Selection Sort
Scenario
You are writing firmware for an IoT sensor that stores calibration data on Flash memory. Flash cells physically degrade and eventually fail after a finite number of write operations.
How do you sort the calibration data while performing the absolute minimum number of memory writes?
Why it exists
Problem: Some storage media (EEPROM, NAND Flash) have asymmetric read/write costs. Reads are virtually free, but writes physically degrade the hardware. Write-heavy sorting algorithms can literally destroy the memory.
Naive approach: Use Bubble Sort or Insertion Sort, which can perform up to O(N^2) swaps or shifts, rapidly consuming the hardware's limited write endurance.
Better idea: Scan the entire unsorted portion to find the minimum element, then perform exactly one swap to place it. This trades O(N^2) comparisons (cheap reads) for a maximum of N-1 swaps (expensive writes).
Mental model
Imagine lining up students by height. Instead of shuffling everyone around, you scan the whole unsorted line with your eyes (reads), find the shortest person, and walk them directly to the front (one swap). Repeat for the remaining line.
The array is divided into a sorted left partition and an unsorted right partition. In each pass, the algorithm scans the entire unsorted partition to locate the absolute minimum element. It then swaps this minimum with the first element of the unsorted partition, growing the sorted partition by one.
Repeated decision: Is this element smaller than the smallest seen so far in the unsorted part?
Explanation
Selection Sort always performs exactly N*(N-1)/2 comparisons, regardless of the input data. Whether the array is already sorted, reverse-sorted, or random, the algorithm executes the same number of comparison operations. It is completely non-adaptive.
However, it performs at most N-1 swaps. Each pass through the inner loop identifies the minimum of the unsorted portion and executes exactly one swap to place it. This makes Selection Sort the optimal choice when writes are expensive.
The loop invariant is: at the start of the i-th iteration, the subarray `arr[0..i-1]` contains the i smallest elements of the original array, in their final sorted positions. Once an element is placed, it is never touched again.
Critically, Selection Sort is NOT stable. The long-distance swap can destroy relative order. Example: `[3A, 3B, 1]`. Finding min=1, we swap it with 3A: `[1, 3B, 3A]`. The relative order of the two 3s has been reversed.
Deep dive
**Is selection sort stable?** — No, the standard implementation of Selection Sort is not stable. Stability means that equal elements retain their original relative order. Selection Sort uses long-distance swaps to move the minimum element into place. If you have an array like `[3A, 3B, 1]`, the algorithm finds the minimum (`1`) and swaps it with the first element (`3A`). The array becomes `[1, 3B, 3A]`. The relative order of `3A` and `3B` has been destroyed.
Selection sort is not stable because long-distance swaps jump over equal elements.
Key points
- Minimum Writes: At most N-1 swaps. The lowest write overhead of any comparison-based sort.
- Non-Adaptive: Always O(N^2) comparisons regardless of input order. It has no mechanism to detect pre-existing sortedness.
- Unstable: Long-distance swaps destroy the relative order of equal elements.
Pattern: Global Minimum Search
Recognition cues:
- The problem explicitly requires minimizing memory writes.
- You need to find the K smallest/largest elements without fully sorting.
Failure signals
- You need a stable sort for multi-key ordering. Selection Sort will corrupt secondary key ordering.
- You are using Selection Sort on a nearly-sorted array. It will still perform O(N^2) comparisons because it cannot detect existing order.
Engineering examples
Flash Memory / EEPROM Firmware
Sorting data on storage with limited Program/Erase cycles.
It minimizes writes to N-1, extending the physical lifespan of the hardware.
K-th Order Statistics
Finding the top K highest-priority items in a scheduler.
Run exactly K passes of Selection Sort to extract the K smallest/largest elements in O(K*N) time without wasting effort sorting the rest.
When not to use
- You need a stable sort: Selection Sort's long-distance swaps destroy relative ordering of equal elements. Use Insertion Sort or Merge Sort instead.
- Data is nearly sorted: Selection Sort is non-adaptive and will always perform O(N^2) comparisons. Insertion Sort handles nearly-sorted data in O(N).
Common mistakes
- Confusing with Insertion Sort: Selection Sort finds the minimum and places it. Insertion Sort takes the next element and inserts it into the sorted partition. Selection Sort's sorted elements are in their FINAL positions; Insertion Sort's sorted elements may shift later.
- Assuming it is stable: The long-distance swap skips over equal elements. [3A, 3B, 1] becomes [1, 3B, 3A], reversing the order of equal elements.
Glossary
- long-distance swap
- Moving an element far away from its original position directly, jumping over other items.
- write overhead
- The amount of extra work the computer has to do just to save or move data in memory.
- comparison-based sort
- An organizing method that works by repeatedly asking 'is A bigger than B?'
Recall questions
- What makes Selection Sort uniquely suited for write-constrained hardware?
- Why is Selection Sort non-adaptive?
- Why is Selection Sort unstable? Give an example.
Questions & answers
Implement Selection Sort.
For each i from 0 to N-2: set min_index = i. For each j from i+1 to N-1: if arr[j] < arr[min_index], update min_index. After the inner loop, swap arr[i] with arr[min_index].
Approach: Selection Sort.
Find the K smallest elements in an unsorted array without fully sorting it.
Run K passes of Selection Sort. After K passes, the first K elements of the array are the K smallest, fully sorted. Time: O(K*N).
Approach: Partial Selection Sort.
Interesting facts
- Selection Sort is the basis for the Heap Sort algorithm. By replacing the linear scan for the minimum with a min-heap extraction (O(log N)), you get an O(N log N) sort with the same minimal-swap philosophy.
Continue learning
Previous: In-Place Operations
Next: Insertion Sort
Related: Bubble Sort
Related: Insertion Sort