Selection sort

The problem it solves

Suppose writes are the expensive thing. You’re sorting records on flash memory with limited write cycles, or each “swap” is physically moving a pallet in a warehouse, or every write triggers an expensive downstream sync. Comparisons are cheap looks; moves cost real money. Selection sort is the comparison sort that minimizes moves: exactly n − 1 swaps, worst case, ever — no comparison sort that actually sorts can promise fewer element placements. It pays for that with maximal, unconditional comparison work, and that trade is the whole algorithm.

It’s also, pedagogically, the cleanest possible expression of “sorting by selection”: find the minimum, place it, repeat. Heap sort is exactly this algorithm with a better find — which makes selection sort the ancestor worth understanding before its descendant makes sense.

The intuition — and where it breaks down

Picking a sports team by height, shortest first: scan the whole line, point at the shortest person, send them to position one. Scan everyone remaining, send the next-shortest to position two. Each scan is exhaustive — you check everyone left, because until you have, you can’t be sure you found the minimum — but each placement is final. Nobody moves twice.

The analogy is honest about the cost structure, which is rare: you really do re-scan people you’ve looked at before, every round, and that repeated looking is the n². Where it breaks: a human scanning a line remembers roughly where the short people are and shortcuts later scans. The algorithm remembers nothing between passes — and can’t, because the one swap at the end of a pass may have moved an arbitrary element into an arbitrary position, invalidating any cached knowledge. That forgetting is why selection sort is non-adaptive: sorted input, reversed input, it does not care. The comparison counter is identical for both, and the visualization’s sorted preset exists to let you watch it not care.

Loading…

A walkthrough you can check

Sort [3, 1, 4, 2].

1. Scan all four: minimum is 1 at index 1. Swap into index 0 → [1, 3, 4, 2]. Three comparisons, one swap.
2. Scan indices 1–3: minimum is 2 at index 3. Swap into index 1 → [1, 2, 4, 3]. Two comparisons, one swap.
3. Scan indices 2–3: minimum is 3 at index 3. Swap → [1, 2, 3, 4]. One comparison, one swap.
4. One element left — already placed. Done: six comparisons (3+2+1), three swaps (n − 1).

Now the instructive variant: sort [1, 2, 3, 4]. Same six comparisons — but watch the swap counter: each pass finds the minimum already in place and skips the swap. Zero swaps, and still every comparison. The prediction prompt asks exactly this (“will a swap happen?”), because the answer trains the eye on where the work actually is.

The invariant

After pass k, the first k positions hold the k smallest values, in final sorted order — permanently. Nothing left of the boundary ever moves again. Contrast insertion sort’s weaker “prefix is sorted so far, subject to shifting”: that difference in invariant strength is precisely why insertion sort can exploit lucky input and selection sort cannot. A strong invariant is bought with unconditional work.

The inner scan carries its own: min always indexes the smallest element seen so far this pass. It’s trivially maintained — one comparison, one conditional update — and it’s the piece heap sort replaces: a heap maintains “minimum of everything remaining” across passes for O(log n) per extraction instead of O(n) per scan. Same skeleton, better data structure, and O(n log n) falls out.

Complexity, derived

Comparisons: pass k scans n − k elements, so Σ(n−1 … 1) = n(n−1)/2, always — best case, worst case, indistinguishable, which the sorted/reversed presets demonstrate side by side. Swaps: at most one per pass, so ≤ n − 1 — this is the headline. Writes: at most 2(n − 1), versus insertion sort’s per-inversion shifting (up to n²/2 writes) and bubble sort’s swap-per-inversion (up to n² writes). If writes dominate your cost model, this “worse” algorithm wins outright.

Space O(1), trivially in place. And one property worth stating before an interviewer asks: the standard array selection sort is not stable. The long-range swap can jump an element over an equal twin — sort [2a, 2b, 1] and watch 2a leapfrog 2b. (A stable variant exists — insert the minimum by shifting rather than swapping — but that reintroduces exactly the writes the algorithm existed to avoid.)

What people get wrong

“It’s basically bubble sort.” They’re both quadratic and that is where the resemblance ends. Bubble sort does O(inversions) swaps and can early-exit; selection sort does ≤ n−1 swaps and can never exit early. On reversed input bubble sort performs ~n²/2 swaps to selection’s n−1; on sorted input bubble exits in one pass while selection grinds every comparison. Lumping them together forfeits both contrasts.

Assuming stability. Covered above; it costs interview points because the plausible-sounding answer is wrong.

Breaking the scan early on “good enough”. The invariant needs the true minimum; stopping at the first small-ish element produces an unsorted array that looks half-right. The exhaustive scan is not optional.

Swapping unconditionally when min == i. Harmless-looking, but it doubles the writes on sorted-ish input — and minimizing writes was the algorithm’s one advantage.

Implementation notes across languages

The algorithm is too small for language traps, so the notes are about the boundary. In Python and JavaScript, min(range) / manual scan is clearer than clever one-liners; readability is the only axis left. In C++, std::min_element plus std::iter_swap is the idiomatic two-liner and communicates intent. The real-world note: selection sort’s honest niche — write-limited media, physical rearrangement, EEPROM wear — is narrow but real, and heap sort is what you say next: “same selection strategy, with a heap making each selection logarithmic”. That one sentence turns a beginner algorithm into a bridge.