Selection sort
Scan the unsorted part for its smallest value and swap it to the front. The sorted part grows by one each time. Like picking the shortest person out of a line, again and again.
53819274
Press play or step forward to start.
1function selectionSort(a) {2 for (let i = 0; i < a.length - 1; i++) {3 let min = i;4 for (let j = i + 1; j < a.length; j++) {5 if (a[j] < a[min]) min = j;6 }7 if (min !== i) swap(a, i, min);8 }9}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n² | every input: it always scans the whole unsorted part |
| average | n² | random input |
| worst | n² | any input, but never more than n − 1 swaps |
| space | 1 | sorts in place |
Where it breaks
- Sorted input does not help. It cannot tell the rest is in order without scanning it. Pick Sorted above: still 28 compares for 8 items, but 0 writes.
- But writes are cheap. It never makes more than n − 1 swaps. When writing is far slower than reading, such as on flash memory, that can matter more than the compares.
- Equal keys can swap order. A long-distance swap can jump one item past an equal one. Pick Duplicates: the 3 that starts at the front is swapped far right and lands behind a 3 that started after it. So it is not stable.