Selection Sort

Selection sort is the textbook example of a quadratic comparison sort built from one of the simplest possible ideas: scan the unsorted region for the smallest element, swap it into the front, repeat. Its time complexity is Θ(n²) in all cases — best, average, and worst — because the scan to find the minimum cannot be short-circuited by encountering already-sorted data. In return for that bleak time profile, selection sort offers one genuine virtue that no other sort matches: it performs at most n − 1 swaps, regardless of input. When the cost model is dominated by writes (think flash memory with limited erase cycles, or EEPROM, or any medium where reading is cheap and writing is expensive or destructive), this write-minimization property promotes selection sort from “pedagogical curiosity” to “the right tool.” Outside that niche, Insertion Sort beats it on every realistic input despite sharing the same Θ(n²) worst case, because insertion sort is adaptive and selection sort is not.

1. Intuition — Drafting Players One Slot at a Time

Picture a roster of basketball players standing in arbitrary order. You want them in a single-file line, sorted shortest to tallest, but you can only manipulate them in one specific way: pick whoever is shortest in the remaining unsorted crowd, walk them to the front of the sorted section of the line, and lock them in place. Then look at the unsorted crowd again, find the shortest of those, and walk them to slot 2. Repeat until the crowd is empty.

That is exactly selection sort. The “sorted section” grows from the left by one slot per pass; the “unsorted crowd” shrinks from the right by one slot per pass. The work done in pass k is the linear-time scan needed to locate the global minimum among the remaining n − k unsorted elements, plus exactly one swap at the end of the scan to drop that minimum into position k. Because every pass costs Θ(n − k) comparisons and there are n − 1 passes, the total comparison count is (n − 1) + (n − 2) + … + 1 = n(n−1)/2 ≈ n²/2 — the closed-form arithmetic-series sum that drives the Θ(n²) time bound.

The crucial conceptual contrast with Insertion Sort is what each pass invests its work in. Insertion sort spends its work placing the next unsorted element into the correct slot of the already-sorted prefix, which is cheap when that prefix is already mostly correct. Selection sort spends its work finding the next element to place, which is expensive regardless of how the prefix looks. There is no shortcut.

2. Tiny Worked Example (n = 5)

Sort [5, 2, 8, 1, 4] ascending.

We use a moving boundary: positions [0..k−1] are the sorted prefix (initially empty), positions [k..n−1] are the unsorted suffix. Each pass scans the suffix, locates the minimum, and swaps it with arr[k].

Pass `k`	Array state at start	Min in suffix `[k..4]`	Swap	Array state at end	Sorted prefix
0	`[5, 2, 8, 1, 4]`	`1` at index 3	`arr[0] ↔ arr[3]`	`[1, 2, 8, 5, 4]`	`[1]`
1	`[1, 2, 8, 5, 4]`	`2` at index 1	`arr[1] ↔ arr[1]` (no-op)	`[1, 2, 8, 5, 4]`	`[1, 2]`
2	`[1, 2, 8, 5, 4]`	`4` at index 4	`arr[2] ↔ arr[4]`	`[1, 2, 4, 5, 8]`	`[1, 2, 4]`
3	`[1, 2, 4, 5, 8]`	`5` at index 3	`arr[3] ↔ arr[3]` (no-op)	`[1, 2, 4, 5, 8]`	`[1, 2, 4, 5]`
4	one element left, trivially sorted	—	—	`[1, 2, 4, 5, 8]`	`[1, 2, 4, 5, 8]`

Final array: [1, 2, 4, 5, 8].

Two observations from this trace that generalize:

The total number of attempted swaps is n − 1 = 4. Two of them happened to be no-ops because the minimum was already at position k. A more careful implementation guards the swap with if min_idx != k:, eliminating these redundant writes — relevant when writes are expensive.
The number of comparisons did not depend on the input at all. Pass 0 made 4 comparisons (scanning indices 1..4), pass 1 made 3, and so on, totalling 10 = 5·4/2 comparisons. Sorting [1, 2, 3, 4, 5] (already sorted) would have produced the exact same 10 comparisons. This is the precise sense in which selection sort is “non-adaptive.”

3. Pseudocode

selection_sort(arr):
    n := length(arr)
    for k := 0 to n - 2:
        min_idx := k
        for j := k + 1 to n - 1:
            if arr[j] < arr[min_idx]:
                min_idx := j
        if min_idx != k:                # guard avoids self-swap (and the write)
            swap arr[k], arr[min_idx]

The outer loop fixes the position being filled (k walks from 0 to n − 2). The inner loop is a pure linear scan that records the index of the smallest element seen so far in min_idx. Because we initialize min_idx := k and start j at k + 1, the inner loop’s invariant is arr[min_idx] ≤ arr[t] for all t ∈ [k..j − 1]. After the inner loop ends with j = n, that invariant becomes arr[min_idx] ≤ arr[t] for all t ∈ [k..n − 1] — the global minimum of the unsorted suffix.

The if min_idx != k guard is the standard write-minimization gate. Without it, swap arr[k], arr[k] still “happens” (both lvalues are read and written), wasting two memory writes per redundant pass.

4. Python Implementation

def selection_sort(arr: list[int]) -> None:
    """In-place ascending selection sort. Stable: NO. Adaptive: NO."""
    n = len(arr)
    for k in range(n - 1):
        min_idx = k
        for j in range(k + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != k:
            arr[k], arr[min_idx] = arr[min_idx], arr[k]

Two style notes for interview presentation. First, the outer loop stops at n − 1 (range goes 0..n−2) because once the first n − 1 slots are fixed, the last slot must contain the largest remaining element by elimination — running an extra pass on a one-element suffix is wasted work. Second, the strict < (not ≤) in the inner-loop comparison is what destroys stability: when there are duplicate values, the algorithm prefers the leftmost occurrence as min_idx, but the swap that follows can fling a later equal element across the leftmost equal element, reversing their relative order (see Pitfalls §10.1 for a concrete example).

5. Complexity Analysis

5.1 Time

Let n be the array length. The outer loop runs n − 1 times. In the iteration with index k, the inner loop runs n − 1 − k times (it scans indices k + 1 .. n − 1). The total number of comparisons is:

C(n) = Σ_{k=0}^{n−2} (n − 1 − k)
     = (n − 1) + (n − 2) + … + 2 + 1
     = n(n − 1) / 2
     = Θ(n²)

where:

Σ denotes summation.
k is the outer-loop index, ranging from 0 to n − 2.
n − 1 − k is the size of the unsorted suffix during pass k.
The closed form n(n − 1)/2 is the standard sum of the first n − 1 positive integers.

Critically, this count does not depend on the input contents — only on n. There is no early-exit condition, no “is the suffix already sorted?” check that could shortcut the scan. So T_best = T_avg = T_worst = Θ(n²).

The number of swaps is at most n − 1 (one per outer-iteration, possibly skipped by the min_idx != k guard). This is asymptotically negligible compared to the comparison cost in a standard cost model where read and write are equally expensive, but it dominates the picture in write-cost-asymmetric models — this is what makes selection sort uniquely interesting (see §6).

5.2 Space

Auxiliary space is Θ(1): the algorithm uses min_idx, the loop counters, and the swap-temp variable — a constant number of scalar variables independent of n. Selection sort is truly in-place, with no recursion stack consumption (it is iterative).

5.3 Why `Θ(n²)` Is Unavoidable Here

Could we do better than n(n − 1)/2 comparisons by being cleverer? Yes, but only by changing the algorithm. Tournament selection (a heap-like data structure) finds the minimum of the suffix in O(log n) comparisons after an O(n) setup, leading to O(n log n) total — and that is exactly Heap Sort in disguise. The vanilla selection-sort recipe — “linear scan to find minimum, swap, repeat” — has no slack to optimize: every comparison on every pass is independently necessary, because the algorithm carries no memory between passes about which suffix elements were already compared to each other.

6. The One Genuine Niche — Write-Asymmetric Storage

In a typical RAM cost model, reads and writes both cost roughly one cycle, so the comparison count dominates and selection sort loses badly to anything else. But on certain media the write cost is dramatically higher than the read cost:

NOR/NAND flash memory — writes are slow and erase cycles are limited (typically 10⁴ to 10⁵ erases per block before wear-out). Minimizing writes extends device life.
EEPROM — similar wear concerns at smaller scales (microcontroller config storage, smartcards).
Phase-change memory (PCM) and other non-volatile memory technologies — write energy is orders of magnitude higher than read energy.
Network or RPC-backed storage — if every “swap” is actually a remote write, the round-trip cost dwarfs comparison cost.

In these regimes the cost model becomes “minimize writes subject to a comparison budget.” Selection sort performs at most n − 1 swaps total (with the self-swap guard, fewer if some minimums are already in place), versus Θ(n²) writes for Insertion Sort in the worst case (every shift is a write) and Θ(n log n) writes for Quicksort and Heap Sort. So among the common sorts, selection sort is the write-minimizer.

It is not, however, the theoretical optimum — a point worth getting right, because the note’s earlier draft overstated it. First, the unit matters: each swap is two writes (read both, write both), so selection sort costs up to 2(n − 1) writes, not n − 1. Second, Cycle Sort does strictly better. Cycle sort writes each element either zero times (if already in its correct final position) or exactly once, for at most n − 1 writes total — and Wikipedia describes it as “theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm” (Cycle sort, Wikipedia). So when the genuine goal is “as few physical writes as possible,” the correct answer is cycle sort, with selection sort as the simpler, more widely known runner-up. Wikipedia frames selection sort’s write advantage only relative to insertion sort (“n − 1 swaps versus up to n(n − 1)/2 swaps”), not as a global optimum (Selection sort, Wikipedia).

A second caveat concerns whether the algorithm-level write count even reaches the physical flash. Modern solid-state storage interposes a Flash Translation Layer (FTL) that performs wear leveling and garbage collection, producing write amplification: “the actual amount of information physically written to the storage media is a multiple of the logical amount intended to be written,” with the write-amplification factor defined as data written to the flash / data written by the host (Write amplification, Wikipedia). Because the factor multiplies the host write count rather than flattening it, halving logical writes still roughly halves physical writes — so selection sort’s advantage survives, but attenuated by a device-specific constant (the write-amplification factor, which cannot drop below 1.0 absent compression) rather than holding exactly. The clean “I made n − 1 swaps so the flash saw n − 1 writes” story is therefore an upper-layer abstraction; the physical count is n − 1 times the WAF. This matters when quoting a concrete lifespan benefit for a specific deployment, but does not overturn the qualitative ranking selection-sort-beats-insertion-sort-on-writes.

This whole topic is worth raising in an interview if asked “when would you ever use selection sort?” — almost every interviewer expects a glib “never” and is delighted to hear the write-minimization story, and you score extra points by noting that cycle sort is the true write-optimal choice.

7. Stability and Adaptiveness

Stable: No. A stable sort preserves the relative order of elements that compare equal. Selection sort is not stable in its standard array form because the swap step can fling a later equal element across an earlier equal element. Concrete example: input [2a, 2b, 1] (with 2a and 2b representing two 2s tagged by their original position). Pass 0 finds the minimum 1 at index 2 and swaps it with arr[0] = 2a, producing [1, 2b, 2a]. The relative order of 2a and 2b is now reversed: 2b precedes 2a, but originally 2a preceded 2b. Stability is lost.

A stable variant exists by replacing the swap with a shift (move all elements between k and min_idx rightward by one), but the shift turns each pass into Θ(n) writes, eliminating the entire write-minimization advantage and degenerating the algorithm into something morally equivalent to insertion sort. So in practice, “selection sort” means the unstable swap version.

Adaptive: No. An adaptive sort runs faster on inputs that are already partially sorted. Selection sort’s comparison count is n(n−1)/2 for any input, period. No matter how nearly sorted the input is, no matter whether you give it [1, 2, 3, 4, 5] or [5, 4, 3, 2, 1], every comparison and every outer-loop iteration is performed. This is its single biggest weakness compared to Insertion Sort, which runs in Θ(n) time on already-sorted input thanks to its early-exit comparison.

8. Comparison with Insertion Sort

These two are the canonical “simple Θ(n²) comparison sorts” pair, and the differences are illuminating:

Property	Selection Sort	Insertion Sort
Worst-case time	Θ(n²)	Θ(n²)
Best-case time	Θ(n²) (always)	Θ(n) (already-sorted input)
Average-case time	Θ(n²)	Θ(n²)
Number of comparisons	exactly n(n−1)/2	varies with input
Number of writes (worst)	n − 1	Θ(n²)
Number of writes (already sorted)	n − 1 (or 0 with self-swap guard)	0
Stable	No	Yes
Adaptive	No	Yes
Online (can sort streamed input)	No	Yes
Inner loop body	scan + compare	shift + compare

The takeaway is that insertion sort dominates selection sort on every realistic metric except worst-case write count. On nearly-sorted data insertion sort’s Θ(n) early-exit is dramatically faster than selection sort’s unwavering Θ(n²). On random data they are both Θ(n²), but insertion sort’s inner loop is slightly tighter and tends to win in practice (Knuth, TAOCP Vol. 3, gives the precise constant comparison). The single column where selection sort wins is worst-case writes, and that column matters only on write-asymmetric storage.

The interview takeaway: prefer insertion sort over selection sort by default. The only time the “selection sort” answer is correct is when the question explicitly asks “minimize writes” or specifies a flash-memory / EEPROM cost model.

9. Variants

9.1 Double-Ended Selection Sort (Min-Max Sort)

Each pass simultaneously finds both the minimum and the maximum of the unsorted suffix in one combined scan, swaps the min to the left boundary and the max to the right boundary, then shrinks the unsorted region from both sides. The inner-loop comparison count drops from n(n−1)/2 to roughly 3n²/4 (each pair of elements requires three comparisons in a balanced min-max tournament — a constant-factor improvement, not an asymptotic one). Implementation needs care: when min and max happen to land at the boundary positions in unfortunate ways, the swap order matters, or the “found” min ends up overwritten by the max swap.

9.2 Stable Selection Sort (Shifting Variant)

Instead of swapping the found minimum with arr[k], slide all elements between k and min_idx one position to the right, then place the minimum at arr[k]. This preserves the relative order of equal elements (stability) but turns each pass into Θ(n) writes — ruining the write-minimization advantage. Rarely used; if you need stability and Θ(n²) is acceptable, use Insertion Sort instead.

9.3 Cycle Sort — the Write-Optimal Cousin

When the only thing you care about is minimizing writes (the §6 niche), Cycle Sort dominates selection sort. It works by following permutation cycles: for each element, count how many elements are smaller than it to compute its final position, then place it there directly, displacing whatever was there and continuing around the cycle until it closes. Each element is written at most once — into its final slot — so the total is at most n − 1 writes, the proven minimum for any in-place comparison sort. The trade-off is more comparisons (it still does Θ(n²) comparison work, and the counting step is itself a scan) and a fiddlier implementation. Selection sort is the simpler write-frugal sort; cycle sort is the optimal one. If an interviewer pushes past “selection sort minimizes writes,” the follow-up answer they are fishing for is cycle sort.

9.4 Heapsort as “Optimized Selection Sort”

Conceptually, Heap Sort is selection sort with a smarter “find the next element” step: instead of scanning the suffix linearly, it maintains a heap so the next maximum (or minimum) can be extracted in O(log n). The two algorithms share the structure “repeatedly find the next extreme and place it at the boundary” — only the data structure backing the find-next step changes. Knuth (TAOCP §5.2.3) presents heapsort within the same chapter as selection sort for exactly this reason.

10. Pitfalls

Forgetting the min_idx != k guard. Without it, every pass executes a swap, even when the minimum is already at position k. On an already-sorted input that means n − 1 self-swaps — 2(n−1) redundant memory writes. On a write-expensive medium this directly wastes hardware lifespan.
Treating < versus ≤ as cosmetic. In the inner loop, if arr[j] < arr[min_idx] keeps min_idx pointing at the leftmost occurrence of the minimum among ties; if arr[j] <= arr[min_idx] would point at the rightmost. Either is unstable in the swap version, but only the leftmost choice gives stability in the shifting variant. Be explicit.
Off-by-one on the outer loop bound. Iterating k to n − 1 instead of n − 2 runs one extra pass on a one-element suffix — harmless but wasted work. Stopping early at k = n − 2 is the canonical idiomatic choice.
Claiming O(n) best case from naïveté. A common interview trap: candidates say “well if the array’s sorted, surely it’s faster?” No — selection sort still does the full n(n−1)/2 comparisons. The shape of the array does not matter.
Assuming stability “because it’s a textbook sort.” Selection sort is not stable in its swap form. If the interview problem requires stable sorting (e.g., sort-by-secondary-key after sort-by-primary), do not reach for selection sort.

11. Diagram

flowchart LR
  subgraph "Pass k: array partition"
    direction LR
    A["[ sorted prefix ]<br/>indices 0 .. k−1<br/>final-position elements"]
    B["[ unsorted suffix ]<br/>indices k .. n−1<br/>scan to find global min"]
  end
  B -->|"linear scan, n−k comparisons"| C["min_idx points at the smallest<br/>element in the suffix"]
  C -->|"swap arr[k] ↔ arr[min_idx]"| D["arr[k] now holds final<br/>k-th smallest value"]
  D -->|"increment k, shrink suffix by 1"| A

What this diagram shows. The lifecycle of one outer-loop iteration of selection sort. The array is conceptually split by a moving boundary at index k into a sorted prefix (whose elements have already been finalized in earlier passes) and an unsorted suffix (still to be processed). The inner-loop scan walks the entire suffix to locate the index of its minimum element, recorded in min_idx. A single swap then drops that minimum into the boundary slot arr[k], finalizing it. The boundary advances by one and the next pass begins. The key insight to take from the diagram is that all of the per-pass work is in the linear scan — the actual swap is a constant-time “decision” at the end. That is why selection sort is non-adaptive and why its time is fixed at Θ(n²).

12. Common Interview Problems

Problem	Source	Why selection sort is or is not the answer
Implement selection sort	Classic warm-up	Demonstrates loop-invariant reasoning, swap mechanics
Sort Colors (Dutch Flag)	LeetCode 75	Selection sort would work in `O(n²)`; optimal is `O(n)` via Dutch National Flag
Find K-th Largest Element	LeetCode 215	A partial selection sort (run `k` passes) gives `O(nk)`; for `k = n/2` use Quickselect for `O(n)` average
Minimize swaps to sort	Several CP / interview variants	Selection sort bounds swaps at `n − 1`; for the true write minimum, Cycle Sort (≤ `n − 1` single-element writes) is optimal
”Sort an array using only swaps where each element is moved at most O(1) times”	EEPROM / wear-bound problems	Selection sort is the canonical simple answer; Cycle Sort is the write-optimal one

The Find K-th Largest framing connects naturally to Quickselect and to a Binary Heap-based top-K solution; selection sort is a useful pedagogical baseline (“the obvious O(nk) answer”) that interviewers expect candidates to mention before improving on.

13. Open Questions

Does the double-ended (min-max) variant deliver measurable wall-clock speedup on modern CPUs, or does branch prediction wash out the 25 % comparison reduction?
Partially resolved (§6): the algorithm-level write count does reach the physical flash, but multiplied by the device’s write-amplification factor (WAF ≥ 1.0), not one-to-one. The reduction relative to O(n²) algorithms is preserved as a ratio but scaled by a deployment-specific WAF. A precise lifespan figure for a named device would still require that device’s measured WAF.
What is the optimal cutoff at which a hybrid sort should switch from a faster algorithm to selection sort for write-cost reasons, e.g., on small-n flash sorts?

14. See Also

Insertion Sort — the strictly-better Θ(n²) sibling on every metric except worst-case writes
Bubble Sort — the third pedagogical Θ(n²) sort; even less practical
Cycle Sort — the write-optimal in-place sort (≤ n − 1 writes); the correct answer when minimizing writes is the true goal
Heap Sort — selection sort with an O(log n) “find next” step backed by a heap
Quicksort — the production O(n log n) average-case comparison sort
Quickselect — partial selection sort generalized to find the k-th element in O(n) average
Binary Heap — backbone data structure for heapsort
Big-O Notation
SWE Interview Preparation MOC

vault

Explorer

Selection Sort

Selection Sort

1. Intuition — Drafting Players One Slot at a Time

2. Tiny Worked Example (n = 5)

3. Pseudocode

4. Python Implementation

5. Complexity Analysis

5.1 Time

5.2 Space

5.3 Why `Θ(n²)` Is Unavoidable Here

6. The One Genuine Niche — Write-Asymmetric Storage

7. Stability and Adaptiveness

8. Comparison with Insertion Sort

9. Variants

9.1 Double-Ended Selection Sort (Min-Max Sort)

9.2 Stable Selection Sort (Shifting Variant)

9.3 Cycle Sort — the Write-Optimal Cousin

9.4 Heapsort as “Optimized Selection Sort”

10. Pitfalls

11. Diagram

12. Common Interview Problems

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Selection Sort

Selection Sort

1. Intuition — Drafting Players One Slot at a Time

2. Tiny Worked Example (n = 5)

3. Pseudocode

4. Python Implementation

5. Complexity Analysis

5.1 Time

5.2 Space

5.3 Why Θ(n²) Is Unavoidable Here

6. The One Genuine Niche — Write-Asymmetric Storage

7. Stability and Adaptiveness

8. Comparison with Insertion Sort

9. Variants

9.1 Double-Ended Selection Sort (Min-Max Sort)

9.2 Stable Selection Sort (Shifting Variant)

9.3 Cycle Sort — the Write-Optimal Cousin

9.4 Heapsort as “Optimized Selection Sort”

10. Pitfalls

11. Diagram

12. Common Interview Problems

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks

5.3 Why `Θ(n²)` Is Unavoidable Here