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
Selection sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n²)
Settings
More options
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 |
Scroll the table sideways for the rest of the columns.
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
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 about n²/2 comparisons whatever the input, and exactly n-1 swaps. That swap count is the fewest of any comparison sort that works in place.
When 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².