Selection sort
Selection sort divides the array into a sorted prefix and an unsorted remainder. For each position, it scans the entire unsorted remainder to find the smallest value there, then swaps that value into place.
When it is the right choice
Selection sort is worth using when writes are far more expensive than comparisons, since it makes at most n − 1 swaps in total, no matter the input. Otherwise it is not competitive: it makes the same number of comparisons on every input — sorted, reversed or random — so it cannot benefit from data that is already partly ordered the way insertion sort can.
How it works
- For each position from the start to the second-to-last, assume the current position already holds the smallest remaining value.
- Scan every later value in turn, comparing each one against the smallest value found so far.
- Whenever a smaller value turns up, remember its position instead.
- After scanning the whole remainder, swap the smallest remaining value into the current position.
Worth noticing
- It always performs the same number of comparisons — Θ(n²) — on sorted, reversed and random input alike, since it must scan the whole remainder every time regardless of order.
- It is not stable: swapping a distant minimum into place can move it past an equal element, changing their relative order.
- Because it makes at most n − 1 swaps in total, it minimises writes even though it does not minimise comparisons.
Cost
- Best
- O(n²)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- No