Selection Sort: Minimizing Swaps
What you'll learn: Why selection sort uses exactly n-1 swaps, making it efficient when writing data is expensive.
The Write-Minimizing Property
Selection sort has a special advantage: it performs the minimum number of swaps possible for any comparison-based sorting algorithm. No matter what the input looks like, selection sort will perform exactly n-1 swaps to sort n elements.
Why Exactly n-1 Swaps?
Think of it this way: you're organizing n items into n positions. Selection sort places one correct item per iteration:
- First pass: find the minimum, swap it into position 0
- Second pass: find the next minimum, swap it into position 1
- ...and so on
After n-1 swaps, n-1 elements are correctly placed. The last element must already be in its correct position (nowhere else to go!), so no final swap is needed.
Contrast with Bubble Sort
Bubble sort can perform many more swaps—up to O(n²) in the worst case. Every time two adjacent elements are out of order, bubble sort swaps them. For a reverse-sorted array, this means swapping nearly every comparison.
Selection sort, however, only swaps once per position, after finding the correct element for that spot.
When This Matters
This property is crucial when:
- Writing to memory is expensive (flash storage, EEPROM)
- Swapping large objects is costly
- Physical operations are involved (imagine sorting physical packages on a conveyor belt—minimizing movements saves time and energy)
Even though selection sort is still O(n²) in comparisons, its predictable, minimal swap count makes it the right choice in write-constrained scenarios.
Key Takeaway: Selection sort guarantees exactly n-1 swaps regardless of input, making it ideal when write operations are expensive, unlike bubble sort which can swap O(n²) times.