Selection Sort
Imagine sorting a shelf of unlabeled boxes by weight. Your only tool is a scale. It compares two boxes at a time and lets you swap any pair. A natural instinct is to find the single lightest box in the whole row. Put it at the front, then repeat on what remains. This is exactly selection sort: repeatedly locate the minimum of an unsorted region and move it into place. It is one of the first algorithms taught precisely because its logic maps so directly onto this physical intuition. No clever trick is required to see why it terminates with a sorted array. Selection sort matters less because of raw performance. It is asymptotically no better than Insertion Sort in the worst case, and typically worse in practice. It matters more because it isolates a single, reusable idea: shrink an unsolved region by repeatedly extracting an extremal element. This "extract-the-min" pattern reappears, refined and accelerated, in far more powerful algorithms. Heapsort is essentially selection sort with the linear scan for the minimum replaced by a logarithmic-time heap extraction. Linear-time selection algorithms attack the narrower question of finding just the k-th smallest element without fully sorting. They use ideas that trace directly back to the selection-sort mindset of partitioning around extremal values. In real systems, selection sort is rarely the production sorting routine. Quicksort, mergesort, and hybrid algorithms dominate there. But it earns its keep in settings where the cost model is unusual. This happens when writes (swaps) are far more expensive than reads (comparisons). Examples include sorting data on flash memory with limited write endurance, or physically moving heavy objects with a robotic arm. In these cases, selection sort's guarantee of at most n−1 swaps total becomes a genuine practical advantage. This beats algorithms that swap on every out-of-order comparison. This article gives a precise statement of the algorithm. It includes a loop-invariant proof of correctness. It also provides a full derivation of its Θ(n²) comparison count. This count holds unconditionally — best case, worst case, average case, all identical. A worked trace shows exactly how the unsorted suffix shrinks. It closes by placing selection sort in the lineage that leads to heapsort and linear-time selection.
- Selection sort repeatedly finds the minimum of the unsorted suffix and swaps it into the next sorted position.
- It performs exactly n−1 passes and always makes at most n−1 swaps total, regardless of input order.
- Comparisons are always Θ(n²): (n−1) + (n−2) + ... + 1, with no best-case speedup — unlike insertion sort.
- Correctness follows from a simple loop invariant: after pass i, the first i elements are the i smallest, sorted.
- It is not stable in its standard swap-based form, though a stable variant exists at extra cost.
- Its "extract the minimum" pattern is the conceptual ancestor of heapsort and linear-time selection algorithms.
Selection sort trades away any chance of a fast best case in exchange for the simplest possible invariant and the fewest possible data movements.
The idea
Selection sort operates on an array `A[0..n-1]` by maintaining a single, growing prefix of sorted, correctly-placed elements at the front. At each step, it examines the remaining unsorted suffix, scans it linearly to find the position of its minimum element, and swaps that minimum into the first slot of the suffix — thereby extending the sorted prefix by one and shrinking the unsorted suffix by one. After n−1 such steps the suffix has shrunk to a single element, which is trivially in place, and the whole array is sorted. The key terminology to fix precisely: a pass is one full scan of the current unsorted suffix to find its minimum. An invariant is a property guaranteed to hold at a specific point in every iteration — here, "the prefix `A[0..i-1]` contains the i smallest elements of the whole array, sorted in increasing order, and every element in it is ≤ every element in the suffix `A[i..n-1]`." The algorithm is a comparison sort: it determines relative order solely through pairwise comparisons, never by inspecting keys' internal structure (unlike, say, Counting Sort). It is also in-place, using only O(1) extra memory beyond the input array and a few index variables. The crucial structural fact — the one that separates selection sort from Insertion Sort despite their shared Θ(n²) worst case — is that the work done per pass is independent of the data. Finding the minimum of a suffix of length m always requires exactly m−1 comparisons, whether the suffix is already sorted, reverse-sorted, or in random order. There is no early exit, no shortcut for lucky inputs. This makes selection sort's comparison count unconditionally Θ(n²): best case, worst case, and average case are the exact same expression, a rarity worth understanding precisely because most algorithms in this course do NOT have that property.
How it works
The algorithm proceeds in n−1 outer iterations. On iteration i (0-indexed, i from 0 to n−2), it treats `A[i..n-1]` as the unsorted suffix, linearly scans it to find the index `m` of its minimum element, and swaps `A[i]` with `A[m]`. ``` SELECTION-SORT(A, n): for i = 0 to n - 2: // n-1 outer passes m = i // assume A[i] is the min so far for j = i + 1 to n - 1: // scan the unsorted suffix if A[j] < A[m]: m = j // remember the new minimum's index if m != i: swap(A[i], A[m]) // place the minimum at front of suffix return A ``` Walking through the mechanics: 1. Outer loop invariant maintenance. Before iteration i begins, `A[0..i-1]` is already sorted and holds the i smallest elements overall. The inner loop's job is purely to locate — not yet move — the minimum of `A[i..n-1]`. 2. Inner loop: linear minimum-finding. `m` is initialized to `i` and updated whenever a strictly smaller element is found. This is a simple running-minimum scan; it costs exactly `(n-1-i)` comparisons for suffix length `n-i`. 3. The single swap. Only one swap is performed per outer iteration (guarded by `m != i` to skip a no-op swap, though this guard is an optimization, not a correctness requirement). This is the defining efficiency feature: at most n−1 swaps total, ever, no matter the input. 4. Termination. After the pass with i = n−2, the suffix `A[n-1..n-1]` has length 1 and is trivially "sorted," so the loop range i = 0 to n−2 suffices; there is no need for an i = n−1 pass. The base case (n ≤ 1) is handled implicitly: the outer loop range `0 to n-2` is empty when n ≤ 1, so the array is returned unchanged, which is correct since arrays of length 0 or 1 are already sorted.
Complexity & correctness
Comparisons — exact and unconditional. On the pass where the suffix has length `n - i`, the inner loop performs exactly `n - i - 1` comparisons to find the minimum. Summing over all outer passes i = 0 to n−2: ``` C(n) = Σ_{i=0}^{n-2} (n - i - 1) = (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 ``` This is Θ(n²) in the best, worst, and average case — all three are literally the same number, `n(n-1)/2`, because the inner loop never terminates early: it must inspect every remaining element to be certain it has found the true minimum. This is the single fact that most sharply distinguishes selection sort from insertion sort, whose best case (already-sorted input) is Θ(n) because its inner loop can exit as soon as it finds the correct insertion point.
Swaps — the actual selling point. At most one swap happens per outer iteration, so the total number of swaps (data movements) is at most `n - 1`, and this bound holds regardless of the input's initial order. Compare this to insertion sort, whose number of shifts can be Θ(n²) on reverse-sorted input, or bubble sort, whose swap count is likewise data-dependent. This is why selection sort is preferred when a swap is expensive (e.g., swapping large records, or physically moving objects) relative to a comparison.
Space. The algorithm uses O(1) auxiliary space: only the loop indices `i`, `j`, and `m`. It sorts in place, requiring no auxiliary array.
Correctness — loop invariant proof. Define the invariant `I(i)`: "Before the start of outer iteration `i`, the subarray `A[0..i-1]` consists of the `i` smallest elements of the original array, arranged in sorted order, and every element of `A[0..i-1]` is ≤ every element of `A[i..n-1]`."
- Initialization: Before iteration i=0, `A[0..-1]` is the empty subarray. The invariant holds vacuously (zero smallest elements, trivially sorted, and the "every element ≤" condition is vacuous).
- Maintenance: Assume `I(i)` holds. The inner loop scans `A[i..n-1]` and correctly identifies index `m` such that `A[m]` is the minimum of that suffix — this is a straightforward induction on the inner loop itself (after examining `A[i..j]`, `m` holds the index of the minimum of that examined prefix, since we always update `m` upon finding something strictly smaller). Swapping `A[i]` and `A[m]` places this suffix-minimum at position `i`. Because `A[m]` was the minimum of the entire suffix `A[i..n-1]`, and by `I(i)` everything in that suffix was already ≥ everything in `A[0..i-1]`, we now have: `A[0..i]` consists of the `i+1` smallest elements overall (the previous `i` smallest, plus the next-smallest which was the suffix minimum), and it is sorted because the newly placed element is ≥ the previous prefix's maximum (by `I(i)`) and ≤ every remaining suffix element (by minimality). This is exactly `I(i+1)`.
- Termination: The outer loop runs for i = 0 up to n−2, so it terminates with `I(n-1)` holding and the last iteration having placed the minimum of the final two-element suffix, giving `I(n)`: `A[0..n-1]` is fully sorted. This is precisely the postcondition required.
This proof is deliberately simple compared to, say, quicksort's partition-correctness argument — that simplicity is the entire pedagogical point of studying selection sort first.
Stability caveat. The textbook swap-based version is not stable: swapping `A[i]` with a distant `A[m]` can jump an equal-valued element past another equal-valued element that was originally to its left, reordering equal keys. A stable variant exists (rotate the minimum into place via repeated adjacent swaps or shifts instead of one long-distance swap) but this raises the movement cost back toward Θ(n²), forfeiting the algorithm's main advantage.
Worked example
Trace `A = [64, 25, 12, 22, 11]`, n = 5. Expect `C(5) = 5·4/2 = 10` comparisons total and at most 4 swaps.
| Pass i | Suffix scanned | Comparisons this pass | Min found (index, value) | Swap performed | Array after pass |
|---|---|---|---|---|---|
| 0 | A[0..4] = [64,25,12,22,11] | 4 | (4, 11) | swap A[0],A[4] | [11, 25, 12, 22, 64] |
| 1 | A[1..4] = [25,12,22,64] | 3 | (2, 12) | swap A[1],A[2] | [11, 12, 25, 22, 64] |
| 2 | A[2..4] = [25,22,64] | 2 | (3, 22) | swap A[2],A[3] | [11, 12, 22, 25, 64] |
| 3 | A[3..4] = [25,64] | 1 | (3, 25) | none (already min) | [11, 12, 22, 25, 64] |
Total comparisons: 4 + 3 + 2 + 1 = 10, matching `n(n-1)/2 = 10` exactly. Total swaps: 3 (pass 3 needed none because `m = i` already). This confirms the bound of at most n−1 = 4 swaps — here even fewer were needed, but the comparison count is fixed at exactly 10 no matter what the input values had been, even if the array had started perfectly sorted as `[11,12,22,25,64]`: the algorithm would still perform all 10 comparisons (it would find `m = i` every time and simply skip every swap), producing zero swaps but the identical 10 comparisons. This is the concrete demonstration of "unconditional Θ(n²) comparisons" promised at the outset — best-case input changes the swap count, never the comparison count.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Off-by-one on outer loop bound | Running the outer loop to `i = n-1` instead of `n-2` causes an inner loop over an empty range, harmless but wasteful; running it to `i < n-2` leaves the array unsorted | Outer loop must cover i = 0 .. n−2 inclusive |
| Forgetting the `m != i` guard has no effect on correctness | Some learners assume skipping self-swaps is required for correctness | It's purely a micro-optimization; swapping an element with itself is a no-op either way |
| Assuming selection sort is stable | It "feels" similar to insertion sort, which can be stable | The long-range swap can invert relative order of equal keys; verify with an explicit example of duplicate keys |
| Expecting a fast best case | Confusing selection sort with insertion sort or bubble sort, which do have Θ(n) best cases | Selection sort's inner scan never exits early — it is Θ(n²) unconditionally |
| Using it for large n in production code | Its simplicity is tempting | For n beyond a few thousand, use Quicksort, mergesort, or a hybrid; selection sort loses badly to O(n log n) algorithms |
:::warning[The stability trap is the most dangerous, because it silently corrupts secondary-key ordering.] If you sort records by one field using selection sort, expecting records with equal keys to retain their prior relative order (as insertion sort or mergesort would guarantee), selection sort can quietly scramble that order via its long-distance swaps — a bug that will not show up in a simple test on distinct keys and can go unnoticed until a downstream process depends on the now-broken secondary order.
Pioneers & history
Selection sort does not have a single celebrated inventor in the way that, say, quicksort is attributed to Tony Hoare; it belongs to the small set of "folklore" algorithms that were independently rediscovered many times because they mirror the most natural manual sorting strategy — repeatedly picking out the smallest remaining item, exactly as a person sorting playing cards or filing folders might do by hand. Its formal analysis, however, is inseparable from the broader development of algorithm analysis as a discipline in the 1950s–60s, when computer scientists began rigorously quantifying comparison counts and data-movement counts as separate cost measures — a distinction essential to appreciating why selection sort is taught at all.
Origins · 1 minDonald E. Knuth and how this was discovered
Where this matters
Selection sort's direct industrial use is limited — it is essentially never the default `sort()` in a production standard library, since those routines (Timsort, Introsort, pattern-defeating quicksort) achieve O(n log n) with far better constants for large n. But its conceptual descendants are everywhere:
- <a class="wiki-link" href="/wiki/cs-algo-heapsort" data-track="wiki_article.body.wiki_link">Heapsort</a> is precisely selection sort with the inner "find the minimum" scan replaced by extracting from a binary heap, dropping the per-pass cost from O(n) to O(log n) and the total time from Θ(n²) to Θ(n log n) — while keeping selection sort's in-place, low-swap character.
- Linear-Time Selection algorithms (quickselect, median-of-medians) directly generalize the "find the k-th smallest without fully sorting" instinct that selection sort embodies in its purest, most repeated-extraction form.
- Flash storage and EEPROM-backed systems, where write endurance is limited, sometimes favor selection-sort-like strategies (or its close cousin, cycle sort) specifically because they minimize the number of write operations, even at the cost of more comparisons.
- Embedded and pedagogical systems with severe memory constraints use selection sort for its O(1) auxiliary space and simplicity, when n is guaranteed small (e.g., sorting a handful of sensor readings on a microcontroller).
- Teaching and interview settings use it as the canonical first proof-of-correctness exercise, because its loop invariant is the simplest nontrivial one a student encounters before tackling insertion sort's shifting invariant or quicksort's partition invariant.
Ask the tutor: How does replacing the linear scan in selection sort with a binary heap turn it into Heapsort, step by step?
Is selection sort ever faster than insertion sort or quicksort in practice?
Rarely, and only under specific cost models. When comparisons are cheap but swaps are extremely expensive — for example, sorting physically heavy objects with a robotic arm, or minimizing writes to flash memory with limited write endurance — selection sort's guarantee of at most n−1 swaps can beat algorithms that swap far more often. For ordinary in-memory numeric or string sorting on modern hardware, its unconditional Θ(n²) comparison count makes it slower than insertion sort on nearly-sorted data, and dramatically slower than O(n log n) algorithms for even moderately large n.
Does selection sort ever benefit from partially sorted input, like insertion sort does?
No. Its inner loop must scan the entire remaining suffix on every single pass to guarantee it has found the true minimum, regardless of how the elements are arranged. This is the key structural difference from insertion sort, whose inner loop can terminate early once it finds the correct insertion point, giving it an O(n) best case on already-sorted input. Selection sort performs exactly n(n-1)/2 comparisons on every input of size n — sorted, reverse-sorted, or random — making its running time entirely independent of input arrangement.
Can selection sort be made stable without losing its low swap count?
Not without a tradeoff. The stable variant inserts the found minimum into position by shifting all intervening elements over by one (like insertion sort's shift), rather than performing a single swap with the far-away minimum. This preserves relative order of equal keys but raises the total data-movement cost from O(n) swaps to potentially O(n²) element shifts, eliminating the main practical advantage that makes selection sort worth choosing in the first place.
How does selection sort relate to Heapsort?
Heapsort can be understood as selection sort with a smarter data structure for finding the minimum (or maximum). Instead of linearly scanning the unsorted region in O(n) time per pass, Heapsort first organizes it into a binary heap, letting each extraction of the extremal element cost only O(log n). This single change transforms the overall running time from Θ(n²) to Θ(n log n) while preserving the core "repeatedly extract the extremum" strategy and the in-place, low-auxiliary-space character of selection sort.
Why do textbooks still teach an algorithm that is asymptotically no better than insertion sort?
Selection sort's value is pedagogical and structural rather than practical. It offers the cleanest possible loop-invariant correctness proof among elementary sorts, has an easily derived exact comparison-count formula, and clearly demonstrates that a comparison count and a swap count are genuinely separate cost measures — some algorithms minimize one at the expense of the other. It also serves as the conceptual seed for Heapsort and for linear-time selection algorithms, so understanding it deeply pays off later even though it is rarely deployed directly.
What is the relationship between selection sort and finding the k-th smallest element (selection problem)?
Selection sort solves the "selection problem" — find the k-th smallest element — as a side effect of each pass: after i passes, the i-th smallest element has just been placed at index i−1. But it does this inefficiently, fully sorting the prefix on the way, costing O(n) work per element found. Linear-Time Selection algorithms like quickselect isolate exactly this sub-problem and solve it in expected O(n) (or worst-case O(n) via median-of-medians) without sorting anything else, directly generalizing selection sort's core "find one extremal element" step.