Selection Sort

Intuition

Selection sort splits the array into two regions: a sorted prefix on the left and an unsorted suffix on the right. Each pass scans the unsorted suffix, picks the smallest value in it, and swaps that value into the first unsorted slot. The sorted prefix grows by one, the unsorted suffix shrinks by one, and the process repeats until the prefix covers the whole array.

The name comes from what each pass does — it selects the minimum of what's left and parks it at the boundary.

How It Works

Two nested loops, with a running "minimum so far" pointer:

• Outer loop counts the pass index i from 0 to n − 2. Slot i is the next position to fill.
• min_idx pointer is initialized to i at the start of every pass. It tracks where the smallest value found so far lives.
• Inner loop sweeps j from i + 1 to n − 1, comparing arr[j] against arr[min_idx]. When a smaller value appears, min_idx updates to j.
• When the inner loop ends, one swap moves arr[min_idx] into arr[i] — if min_idx actually moved. The guard if min_idx != i skips the swap when the current slot already held the minimum.

The key invariant: after pass i, the first i + 1 cells hold the i + 1 smallest values in sorted order. Unlike bubble sort, the sorted region grows on the left, not the right.

Step By Step

For the default input [64, 25, 12, 82, 37, 49, 15]:

1. Pass i = 0. min_idx = 0 (value 64).
2. Sweep j. 25 < 64 → min_idx = 1. 12 < 25 → min_idx = 2. 82, 37, 49 don't beat 12. 15 > 12 either.
3. Swap arr[0] and arr[2] → [12, 25, 64, 82, 37, 49, 15]. The 12 cell turns green — settled at its final position.
4. Pass i = 1. min_idx = 1 (value 25). Sweep finds 15 at index 6 → min_idx = 6. Swap → [12, 15, 64, 82, 37, 49, 25].
5. Pass i = 2. min_idx = 2 (value 64). Sweep finds 25 at index 6 → swap → [12, 15, 25, 82, 37, 49, 64].
6. Pass i = 3. Minimum of [82, 37, 49, 64] is 37 → swap → [12, 15, 25, 37, 82, 49, 64].
7. Pass i = 4. Minimum of [82, 49, 64] is 49 → swap → [12, 15, 25, 37, 49, 82, 64].
8. Pass i = 5. Minimum of [82, 64] is 64 → swap → [12, 15, 25, 37, 49, 64, 82]. Done.

In the visualization, watch the min pointer chase the smallest bar across the unsorted region. The swap fires exactly once per pass — that's the visual signature that distinguishes selection sort from bubble sort, which swaps many times per pass.

Complexity

Space: O(1) — sorting happens in place.

Number of swaps: O(n). This is selection sort's one selling point. Comparisons are still n(n − 1) / 2, but swaps are bounded by n − 1 because each pass performs at most one swap. If swapping is much more expensive than comparing — large records, slow I/O — selection sort can beat bubble sort and insertion sort on real wall-clock time even though all three are O(n²).

The cost: selection sort is not adaptive. It runs the full inner sweep regardless of whether the array is already sorted. Insertion sort, which short-circuits on a partially sorted input, beats it on nearly-sorted data.

Edge Cases

• Empty or one-element array — outer loop runs zero times, the array is returned as-is.
• Already sorted input — every pass finds the minimum at index i, so the min_idx != i guard skips the swap. Comparisons still run the full O(n²).
• All equal values — every comparison fails the < check, so min_idx never moves and no swaps fire.
• Duplicates — selection sort is not stable. The single swap per pass can fling an equal-valued element across other duplicates, reversing their original order. The canonical counter-example: [2a, 2b, 1] sorts to [1, 2b, 2a] — the swap on pass 0 jumps 2a past 2b.

Common Mistakes

• Forgetting to reset min_idx at the top of each pass. Without min_idx = i, the pointer carries the previous pass's value and the algorithm searches the wrong region.
• Comparing against arr[i] instead of arr[min_idx]. Doing so loses track of the running minimum — you'd always swap with the first smaller value seen, which is bubble sort's behavior, not selection sort's.
• Swapping unconditionally. Without the min_idx != i guard, a pass where the current slot already holds the minimum still performs a no-op swap. Functionally harmless, but it wastes work and obscures the algorithm's "one swap per pass at most" property.
• Assuming it's stable. Production code that needs stable sorting of records by key must use insertion sort, merge sort, or Timsort instead.