Selection sort also builds a sorted prefix one element at a time, but it grows that prefix the opposite way from insertion sort. Instead of pulling the next original element out and shifting sorted neighbors to make room, it scans the entire unsorted remainder for its minimum, then swaps that minimum straight into the next open slot. The sorted prefix never has to shift again once an element lands in it — every pass writes to at most two array slots.
Enter a comma-separated list of numbers, then step through the sort. Bars in the shaded region are the sorted prefix; the bordered bar is the scan cursor; the filled accent bar is the current minimum-so-far; two accent bars appearing together mark a swap.
The invariant is stronger than insertion sort's: before each pass, the first
i elements of the array hold the i smallest values in the whole array,
already in sorted order. Insertion sort's sorted prefix only holds "whichever elements
happened to come first, sorted among themselves" — it can still contain the array's largest
value if that value showed up early. Selection sort's prefix can't: each pass explicitly hunts
down the true minimum of everything not yet placed (tracked as minIdx, starting at
the pass's own index i and updated whenever a smaller element turns up) and puts it
at the front. One swap between i and minIdx finishes the pass — no
matter how far the minimum was from where it needed to be, it takes exactly one write to get
there.
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx !== i) {
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
}
return arr;
}
No adaptive best case. Insertion sort finishes early on already-sorted
input — its inner loop never fires. (Bubble sort has the same property, comparing adjacent pairs
and stopping a pass early once no swap occurs — see bubble sort.) Selection
sort has no such shortcut: the scan for the minimum has to look at every remaining element on
every pass
regardless of whether the array is already sorted, so it always makes exactly
n(n-1)/2 comparisons. Checked directly against the reference implementation above:
an ascending run, a descending run, a random shuffle, and an all-equal array of the same length 7
all produced exactly 21 comparisons — the count genuinely doesn't depend on input order, only on
n.
What does vary: the swap count, and only that. Selection sort makes at most
n - 1 swaps total — one per pass, skipped entirely when minIdx === i
already. The same four length-7 inputs above needed 3, 0, 3, and 0 swaps respectively, all well
under the n - 1 = 6 ceiling.
The ceiling isn't reached the way "every out-of-place element costs a swap" would
suggest. Checked directly against the reference implementation above at n =
5,000: a reverse sorted array — every single element out of place —
needs only 2,500 swaps, exactly n / 2, not the full n - 1 =
4,999. A strictly descending array pairs up symmetrically around its center, so each swap
places two elements correctly at once (the minimum moving into index i carries the
old occupant of i straight to the slot it belongs in too), halving the
count. A random array is the case that actually approaches the ceiling: eight
trials at the same n landed between 4,989 and 4,993 swaps, because there's no
symmetry for minIdx to land on i by coincidence. That's the real reason
to reach for this algorithm over insertion sort when writes are expensive (flash memory, large
records with a cheap-to-compare key) — and it's now a measured number, not a hand-wave:
insertion sort's own reference
implementation makes exactly 12,502,500 writes sorting the same n = 5,000
reverse-sorted array — its worst case too. Selection sort's 2,500 swaps cost 2 writes each (one
per side of the exchange), 5,000 writes total: about 2,500× fewer, on the one
input both pages already call out as their shared worst case for comparisons.
The naive swap breaks stability. Take [3♥, 5, 3♦, 1], where
♥ and ♦ tag two cards that compare equal. Pass one scans for the minimum, finds 1
at index 3, and swaps it with index 0 — but that same swap also yanks 3♥ from the
front of the array all the way to the back, jumping clean over 3♦, which never
moves. The result: [1, 5, 3♦, 3♥] — the two equal cards changed relative order,
confirmed by running the exact swap logic above on tagged values, not just asserted. Insertion
sort's shift-based approach never has this problem (see its own Pitfalls section); selection
sort's swap-based approach always can, whenever an element equal to the pass's minimum sits
between i and minIdx.
Time: O(n²) in every case — best, average, and worst all make
the same n(n-1)/2 comparisons, with no input that finishes early.
Space: O(1) extra — it sorts in place, the same as insertion sort.
Swaps: at most n - 1, and often fewer — a genuine advantage over
every O(n log n) comparison sort on this site, though not the strongest one anymore:
Cycle Sort shares the same O(n²) time
floor and pushes the same idea to its provable minimum, writing every element at most once
instead of merely "often fewer" times.
For the same idea — repeatedly extract the extreme value of the unsorted remainder and place
it — with the O(n) linear scan replaced by an O(log n) heap
extraction, see heap sort: it finds the maximum instead
of the minimum and grows its sorted region from the right instead of the left, but the underlying
move is the same, and trading the scan for a heap is exactly what turns selection sort's
O(n²) into heap sort's guaranteed O(n log n). See Choosing a Comparison Sort for how this site's
twelve comparison sorts stack up against each other, including when selection sort's write-count
guarantee is the actual reason to pick it.