Picking the shortest kid each time
Selection Sort
The analogy
Scan the whole line and find the very shortest kid, then bring them to the front. Now scan the rest, find the shortest of those, put them second. You look a lot but you barely move anyone — one swap per round.
Visualizer
Watch it select
step 1 / 545
3
8
1
9
2
7
4
8 numbers, out of order. Press play — or step through one comparison at a time.
📖 In depth — the full reference
The sorting scoreboard (for reference across all five sorting lessons)
| algorithm | best | average | worst | extra space | stable? |
|---|---|---|---|---|---|
| bubble | O(n) with early exit | O(n²) | O(n²) | O(1) | yes |
| selection | O(n²) — always | O(n²) | O(n²) | O(1) | no (long-range swaps) |
| insertion | O(n) on sorted input | O(n²) | O(n²) | O(1) | yes |
| 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²) (bad pivots) | O(log n) stack | no (typical) |
| Timsort (stdlib) | O(n) | O(n log n) | O(n log n) | O(n) | yes |
Selection sort — everything worth knowing
- Invariant: after pass k, the k SMALLEST values sit in final position at the left — the mirror of bubble's invariant.
- Always O(n²), even on sorted input: it cannot know the minimum without scanning the whole unsorted region. No early exit exists.
- Its one superpower: at most n−1 swaps, the minimum possible for an in-place sort. When a "swap" is monstrously expensive (flash memory writes, huge records moved by robots), selection sort is genuinely used.
- NOT stable: the long-range swap can fly the minimum over an equal element. (A stable variant inserts instead of swapping — but then it is insertion sort with extra steps.)
- Heapsort (Module 5) is selection sort with a better "find the minimum": a heap answers in O(log n) instead of O(n), turning n passes × n scan into n × log n.
Python corner
- min(xs) and xs.index(...) hide inside every selection pass — but calling them per pass is still O(n²) total. Idiomatic Python reaches for sorted() and moves on.
- The "scan the rest, remember the best" pattern outlives the sort: best = min(candidates, key=score) is selection sort's inner loop, used daily.
def selection_sort(a):
n = len(a)
for i in range(n - 1):
lo = i
for j in range(i + 1, n):
if a[j] < a[lo]:
lo = j
a[i], a[lo] = a[lo], a[i] # one swap per round
return aCheck yourself
How many swaps does selection sort make?
Practice — write it yourself
selection_sort(arr): each pass, FIND the minimum of the unsorted region, then swap it into place. One swap per pass — that is its signature. (No sorted() allowed!)
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser