Selection sort
Scan the unsorted remainder for the smallest element, swap it to the front of that remainder, and repeat on what is left. The scan has no early exit — there is no way to know an element is the smallest without looking at all the others — so the comparison count is n−1 then n−2 and so on, which is n(n−1)/2 for every input of size n. The curve plots comparisons, which is what every textbook bound for a sort is about and what makes the four of them directly comparable. The moves are counted too and shown in the panel beside it — worth a look on merge sort, whose comparison count hides the fact that it touches every element on every level.
The claim being tested
O(n²)
When it is the right choice
Almost never for speed, and occasionally for the one thing it is good at: it performs at most n−1 swaps, which is the fewest of any comparison sort here. If moving an element is far more expensive than comparing two — large records, a slow medium — then a sort that compares eight million times and moves four thousand can beat one that does less of both in total.
How it works
- Look at the whole list as an unsorted remainder.
- Scan the remainder and remember where the smallest element is.
- Swap it with the first element of the remainder.
- Shrink the remainder by one and repeat until it is empty.
Worth noticing
- Put this on the same axes as merge sort — the second preset does it — and at n = 4,096 one curve is at 8,386,560 comparisons and the other at 44,004, a factor of 191. They are 28 against 17 at n = 8. That divergence is the entire practical content of the phrase "asymptotically better".
- All three shapes give the same count, to within the handful of swaps. Load each in turn and the curve does not move, which is the control that makes insertion sort’s three curves meaningful.
- The measured gradient comes out at 2.02 and the fit against n(n−1)/2 is exact — a deviation of zero at every size — because this count is not an estimate of a quadratic, it is exactly one. The 0.02 is the −1 in n(n−1) still worth something at these sizes, which the verdict says rather than rounds away.
Cost
- Best
- O(n²)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- n is
- the length of a list of numbers
- Measures
- shuffled: up to n = 4,096; sorted: up to n = 4,096; reversed: up to n = 4,096
The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.
A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.