Sorting

Selection Sort

A comparison-based sorting algorithm that repeatedly selects the minimum element from the unsorted portion.

What is Selection Sort?

Selection Sort divides the input array into two parts: a sorted sublist built up from left to right, and an unsorted sublist. It works by repeatedly finding the minimum element from the unsorted sublist and swapping it with the first element of the unsorted sublist, expanding the sorted boundary.

Key Characteristics:

  • Unstable sort: may change relative order of equal items.
  • In-place: O(1) auxiliary memory.
  • Performs exactly N swaps in worst case (constant write overhead).
  • Independent of initial ordering: always takes O(N^2) comparisons.

Complexity Analysis

Avg Time Complexity: O(N^2) for all cases
Space Complexity: O(1) auxiliary memory
Best Case: O(N^2) comparisons, O(1) swaps
Worst Case: O(N^2) comparisons, O(N) swaps

How it Works Step-by-Step

  1. Set Boundary: Loop index i from 0 to N-2.
  2. Scan Min: Assume array[i] is minimum. Loop index j from i+1 to N-1 to find the actual minimum element in the unsorted range.
  3. Update Min Index: If array[j] < array[min_idx], set min_idx = j.
  4. Swap: Swap array[i] with array[min_idx]. Repeat until array is fully sorted.

Code Implementation

Worked Trace Example

Sorting [29, 10, 14, 37]:
1. Pass 1 (i=0): Unsorted is [29, 10, 14, 37]. Min is 10. Swap 29 and 10 -> [10, 29, 14, 37].
2. Pass 2 (i=1): Unsorted is [29, 14, 37]. Min is 14. Swap 29 and 14 -> [10, 14, 29, 37].
3. Pass 3 (i=2): Unsorted is [29, 37]. Min is 29. No swap -> [10, 14, 29, 37].
Result: Sorted array [10, 14, 29, 37].

Ready to Understand Selection Sort Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Selection Sort Visualizer →