What selection sort does
Each round, selection sort selects the minimum of the unsorted range and puts it at the front of that range.
- Assume the first number of the range is the minimum.
- Scan the rest from left to right, updating the minimum whenever a smaller value appears.
- When the scan ends, swap the minimum with the first number of the range.
- Shrink the range by one (the left cell is now sorted) and repeat until one number is left.
How it differs from insertion and bubble sort
Selection sort always makes the same number of comparisons whatever the data, but very few swaps. Switch between the preset inputs and you will see comparisons stay at n(n − 1) / 2 while swaps never exceed n − 1.
Complexity
| Best | O(n²) |
|---|---|
| Average | O(n²) |
| Worst | O(n²) |
| Extra space | O(1) |
| Stable | No |
FAQ
- Why is the best case of selection sort still O(n²)?
- Every round must scan all remaining numbers to be sure of the minimum, so it always makes n(n − 1) / 2 comparisons regardless of the input.
- What is selection sort good for?
- It performs at most n − 1 swaps. When writing is much more expensive than comparing, it can beat other O(n²) sorts.
- Is selection sort stable?
- No. Swapping the minimum to the front can change the relative order of equal values.