What is selection sort?
Selection sort splits the array into a sorted region at the front and an unsorted region behind it. On every
pass it scans the entire unsorted region to find the smallest remaining value, then
swaps that value into the front of the unsorted region — growing the sorted region by exactly one
element. It always takes n - 1 passes and always scans the full unsorted region on each one, so it's
always O(n²) — but it never performs more than n - 1 swaps in total.
- Unsorted region
- The part of the array from the current position to the end that hasn't been placed yet
- Minimum candidate
- The smallest value found so far while scanning the unsorted region
- Pass
- One full scan of the unsorted region, ending in exactly one swap (or none)
Why selection sort at all?
Picture a scattered pile of playing cards face up on a table, and an empty line you're building next
to it. Each round you scan the whole pile for the smallest card, then move just that one
card to the end of your line.
You never touch two cards more than the comparisons force you to, and a card only ever moves once it's actually found — never speculatively. Compare that to a sort that nudges values one step at a time on every pass; selection sort commits to a single move per pass.
Scan the whole pile before committing to a move.
What does one pass look like?
Every pass is really two separate steps. First find the minimum, only then move it — the two never happen at the same time.
Scan for the minimum
A scan pointer walks the unsorted region one index at a time. A separate min pointer
only moves when scan finds something smaller than the current best — most positions get
checked and rejected.
min only moves when scan finds something smaller.
Swap it into place
Once the scan is finished, there's exactly one move: swap the minimum directly with the front of the unsorted region. Nothing else in the array is touched — not even the values that sat between them.
One swap, no shifting of anything in between.
From one pass to the full sort
The pass you just saw is the whole algorithm — it just repeats, with the sorted region growing by one element and the unsorted region shrinking by one, every single time.
One pass
Track the index of the minimum as you scan, then swap once at the end — never mid-scan. The swap is skipped entirely if the minimum is already at the front.
One scan, at most one swap, every pass.
function selectionSortPass(arr: number[], sortedEnd: number): number {
let minIndex = sortedEnd;
for (let scan = sortedEnd + 1; scan < arr.length; scan++) {
if (arr[scan] < arr[minIndex]) {
minIndex = scan; // found a new minimum
}
}
if (minIndex !== sortedEnd) {
[arr[sortedEnd], arr[minIndex]] = [arr[minIndex], arr[sortedEnd]];
}
return sortedEnd + 1; // sorted region grows by one
}
Every pass
Run the pass again with sortedEnd one higher each time. After n - 1 passes the sorted region
covers the whole array — the last element is already correct by elimination.
4 passes, 3 swaps — one fewer than the array length.
function selectionSort(arr: number[]): number[] {
for (let sortedEnd = 0; sortedEnd < arr.length - 1; sortedEnd++) {
let minIndex = sortedEnd;
for (let scan = sortedEnd + 1; scan < arr.length; scan++) {
if (arr[scan] < arr[minIndex]) {
minIndex = scan;
}
}
if (minIndex !== sortedEnd) {
[arr[sortedEnd], arr[minIndex]] = [arr[minIndex], arr[sortedEnd]];
}
}
return arr;
}
Where it earns its keep — and where it never speeds up
Selection sort's swap count is provably minimal. Its comparison count is not — it pays the same O(n²) price whether the array is scrambled or already sorted.
Guarantees the fewest possible swaps
Each pass does at most one swap, so the whole sort never touches more than n - 1 elements. When writes are expensive — flash memory, EEPROM, anything with a limited write cycle — that guarantee matters more than the O(n²) comparison count.
Never speeds up, even on sorted input
Bubble sort and insertion sort can detect "nothing moved this pass" and stop early on sorted data. Selection sort has no such signal — every pass scans to the end just to confirm the minimum, so it never beats O(n²), not even in the best case.