Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Sorting

Selection Sort Visualiser

Find the smallest value left, swap it into place, repeat.

Starting order

Find the smallest bar left, put it next, repeat.

Comparisons
0
Writes
0
for scale
n² = 196
AverageO(n²)extra space O(1)

The scan runs in full whatever the values are, so this count never moves: it is always n(n−1)/2, half of n². The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.

  • Being compared
  • Being written
  • Pivot or smallest so far
  • In its final place
  • Ruled out
function selectionSort(a) {
for (let i = 0; i < a.length - 1; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) min = j;
}
if (min !== i) {
[a[i], a[min]] = [a[min], a[i]];
}
}
return a;
}

The highlighted line is the one that produced the picture on the left.

What Selection Sort does

Selection sort divides the array into a sorted left part and an unsorted right part. Each pass scans the whole unsorted part for the smallest value and swaps it to the front of that part. The scan is the expensive bit; the swap costs nothing by comparison.

How it works, step by step

  1. Point at the first unsorted position and assume the value there is the smallest.
  2. Scan every remaining value, remembering the index of the smallest one found so far.
  3. Swap that smallest value into the unsorted position. It is now in its final place.
  4. Move the boundary one step right and scan again, over a list that is one shorter.

What to watch for

  • The comparison counter climbs at the same rate no matter what the input looks like: a sorted array costs exactly as much as a shuffled one.
  • The write counter stays tiny. Selection sort does at most n−1 swaps in total, which is why it is used where writing is expensive.
  • A swap can jump a value over many others at once, which is exactly why the sort is not stable: equal values can end up in a different order than they started.

Cost

Best caseO(n²) — the scan always runs in full
AverageO(n²)
Worst caseO(n²)
Extra spaceO(1)
StableNo

When to reach for it

When writes cost far more than reads — writing to flash memory, for instance — and the array is small. Otherwise insertion sort beats it on almost every input, because selection sort cannot take advantage of data that is already nearly in order.

Read more