How Selection Sort Works
Selection sort scans for the smallest remaining value and swaps it into place, using exactly n-1 swaps whatever the input. See why that makes it predictable but not fast.
- Waiting
- Being compared
- Just moved
- In final position
Step 1 of 97
Selection sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n²)
Settings
Two to 48 numbers. Sorted in exactly the order you type them.
Selection sort
- 1
for i in 0..n-2: - 2
min = i - 3
for j in i+1..n-1: - 4
if a[j] < a[min]: - 5
min = j - 6
swap(i, min) - 7
// a[i] is now final
The same array, every algorithm
Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.
- Merge3344 writes
- Quick3340 writes
- Insertion4042 writes
- Shell4637 writes
- Heap5166 writes
- Bubble6062 writes
- Selection6618 writes
How the seven compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
No best case: it scans the whole remaining region even when the array is already sorted. In exchange it never does more than n-1 swaps.
How selection sort works
Selection sort finds the minimum of the unsorted region, swaps it into the region's first position, and shrinks the region by one. It always performs the same number of comparisons — about n²/2 — regardless of the input, and exactly n-1 swaps, which is the fewest of any comparison sort that works in place.
- Point at the first position of the unsorted region.
- Scan the whole region, remembering the index of the smallest value seen.
- Swap that value into the position being pointed at, unless it is already there.
- Advance the pointer by one. Everything to its left is final.
- Repeat until one element remains.
Implementation
The same algorithm the visualiser is running, written to be read.
def selection_sort(values):
n = len(values)
for start in range(n - 1):
smallest = start
for i in range(start + 1, n):
if values[i] < values[smallest]:
smallest = i
# One swap per pass, and only when it changes something.
if smallest != start:
values[start], values[smallest] = values[smallest], values[start]
return valuesWhen to use it
- Use it when writes are expensive and reads are cheap — flash memory, or records so large that moving one costs far more than comparing two. n-1 swaps is hard to beat.
- Use it when predictable timing matters more than speed: it takes the same time on every input of a given size.
- Avoid it as a general sort. It cannot exploit existing order at all, so even a sorted array costs the full n².
Check yourself
If the animation made sense, these should too.
Selection sort has no best case. Why not?
Because finding the minimum of the unsorted region means scanning all of it, and nothing about the scan depends on what it finds. An already sorted array costs exactly the same as a reversed one: about n²/2 comparisons.
When is it the right choice despite being quadratic?
When writing is far more expensive than reading. It does at most n-1 swaps - the fewest of any in-place comparison sort - so on flash memory, or with records so large that moving one costs much more than comparing two, its write count wins.