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. That's the actual reason to reach for this algorithm
over insertion sort: when writes are far more expensive than comparisons (flash memory, large
records with a cheap-to-compare key), selection sort's write count is bounded by the number of
elements actually out of place, not by how far each one has to travel.
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
eleven comparison sorts stack up against each other, including when selection sort's write-count
guarantee is the actual reason to pick it.