Selection Sort

Selection sort repeatedly picks the smallest remaining element and places it next; O(n^2) but with the fewest possible writes.

Select the minimum, repeat

Selection sort divides the array into a sorted prefix and an unsorted suffix. Each round it scans the suffix to find the minimum element and swaps it into the first unsorted slot, growing the sorted prefix by one. After n-1 rounds the array is sorted.

Cost

Finding the minimum of a suffix of length k costs k comparisons, and summing over all rounds gives O(n^2) comparisons regardless of the input, including already-sorted data. The distinguishing feature is that it performs only O(n) swaps, one per round, which matters when a write is far more expensive than a comparison.

• Comparisons: O(n^2) in all cases
• Swaps: O(n) — the fewest of the simple sorts
• Extra space: O(1); stable: no (the standard version)
• Not adaptive: sorted input costs the same as random

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]

Stability and heap selection

The textbook version is not stable because the long-distance swap can jump an element past an equal key. A stable variant that shifts rather than swaps exists but loses the low-swap advantage. Replacing the linear minimum scan with a heap that extracts the minimum in O(log n) turns selection sort into heapsort, which is the natural evolution of the idea.

When minimal writes matter

Selection sort's one-swap-per-round property makes it attractive when writes wear out the medium or dominate cost, as in some flash-memory settings. Otherwise it is dominated by insertion sort, which is adaptive and stable, and by the O(n log n) sorts for anything but tiny arrays. Its predictable comparison count also makes it a clear teaching example for reasoning about loop invariants.