Sorting

Selection Sort

Repeatedly find the smallest remaining value and move it to the front — the fewest swaps any sort can make.

Green is the locked-in sorted prefix — the invariant. Blue is the value currently being scanned. Orange is the smallest value found so far this pass.

What you're seeing

Each bar is a number; taller is larger. Selection sort makes one pass per slot, left to right. On each pass it scans the entire unsorted tail to find the single smallest value (the orange bar tracks the current winner as the blue scanner sweeps right), then swaps that value into the next open slot at the front. The green prefix grows by exactly one — and it never changes again.

Unlike insertion sort, the work per pass is fixed: it always scans the whole remaining tail, no matter how the data is arranged.

The rule

selection_sort(a):
    for i = 0 .. n-2:
        min = i
        for j = i+1 .. n-1:        # scan the unsorted tail
            if a[j] < a[min]:
                min = j
        swap(a[i], a[min])         # move the smallest to the front

It counts a comparison for every a[j] < a[min], and at most one swap per pass.

The invariant

At the start of pass i: a[0..i) holds the i smallest values of the whole array, in sorted order, and every one of them is ≤ every value still in the tail. It is vacuously true at i = 0 (an empty prefix). Each pass keeps it: scanning the tail finds the true minimum of what remains — which is therefore the (i+1)-th smallest overall — and placing it at index i extends the sorted, "all ≤ the rest" prefix by one. When i = n−1, the prefix is the entire array. Because the placed element is the global minimum of the remaining tail, selection sort never has to revisit a slot once filled.

The cost

BestAverageWorst ComparisonsΘ(n²)Θ(n²)Θ(n²) Swaps0O(n)n−1 SpaceO(1)O(1)O(1)

The comparison count is (n−1) + (n−2) + … + 1 = n(n−1)/2 — always, regardless of the input. That is selection sort's defining trait: try Already sorted and the comparison counter is identical to Reversed; it is not adaptive. What it minimizes instead is data movement: at most n−1 swaps total, the fewest of any comparison sort. The standard in-place version is not stable (a long-distance swap can reorder equal keys).

In the wild

Selection sort is almost never the right general-purpose sort — its Θ(n²) comparisons doom it on large inputs, and adaptive sorts crush it on real data. Its one genuine edge is the n−1 swaps bound: when a write is far more expensive than a compare — sorting records by a key while moving bulky payloads, or minimizing writes to flash/EEPROM — minimizing moves can matter. Its deeper legacy is conceptual: heapsort is selection sort done well, replacing the Θ(n) linear scan for the minimum with an O(log n) extraction from a heap, turning Θ(n²) into Θ(n log n).

Try this

Set Initial order to Already sorted and watch the comparison counter — it doesn't drop at all. Now compare that with insertion sort on the same input, where it collapses to linear. That gap is the difference between a non-adaptive and an adaptive algorithm.

References

  1. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), Problem 2-2 (selection sort) and Ch. 6 (heapsort as its efficient cousin). MIT Press, 2022.
  2. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, §5.2.3 (Sorting by Selection). Addison-Wesley.
  3. Sedgewick & Wayne. Algorithms, 4th ed., §2.1 — selection sort: ~n²/2 compares, n exchanges; not stable. algs4.cs.princeton.edu/21elementary.