Lesson 13 · Core algorithms

Selection Sort: Scan, Swap and Cost

Find the smallest value in the unsorted region, swap it into the boundary, and move the boundary right — exactly n−1 times.

The Sorted Boundary

Selection sort repeats one move until the array is sorted:

Scan walk the unsorted region a[i..n-1] and remember where the smallest value sits.
Swap exchange that value with the one at the boundary a[i]. One write, no matter how far it travelled.
Advance move the boundary right by one. The prefix is now sorted and final.
Repeat n−1 times. The last element needs no round; with everything else placed, it is correct by elimination.

Behind that move is a single invariant: everything left of index i is sorted and already in its final position, and everything from i onward is untouched. Each round moves the boundary one step right.

The difference from bubble sort is when values move. Bubble sort swaps constantly during a pass; selection sort scans the entire suffix changing nothing, then performs exactly one swap. Values are chosen, not nudged.

Invariant: a[0..i-1] is sorted and final; a[i..n-1] is untouched
Each round does one full scan and at most one swap
The boundary moves left to right, one position per round
After n−1 rounds the last element is already correct by elimination

Why the Comparison Count Never Changes

Round 1 scans n−1 candidates, round 2 scans n−2, and so on. The total is again n(n−1)/2 comparisons — Θ(n²) in every case.

There is no way to shortcut this. Finding a minimum requires looking at every remaining value; you cannot know an element is smallest without comparing it against all the others. So unlike bubble or insertion sort, selection sort has no best case. Sorted input costs exactly as much as reversed input.

What it does have is a swap guarantee. Every round performs at most one swap, so the total is at most n−1 swaps — dramatically fewer than bubble sort's possible n²/2. When a write is far more expensive than a read, that ratio is the whole argument.

Selection sort across every input
Metric	Best	Average	Worst
Comparisons	n(n−1)/2	n(n−1)/2	n(n−1)/2
Swaps	0	≤ n−1	n−1
Time	O(n²)	O(n²)	O(n²)
Space	O(1)	O(1)	O(1)

Comparisons are Θ(n²) on every input — no adaptive case exists
Swaps are bounded by n−1, the lowest of the simple sorts
Useful when writes cost far more than reads, such as flash memory
The scan cannot terminate early without missing a smaller value

Implementation

Sort with selection sort

def selection_sort(values):
    n = len(values)
    for i in range(n - 1):
        smallest = i
        # scan the unsorted suffix for the index of its minimum
        for j in range(i + 1, n):
            if values[j] < values[smallest]:
                smallest = j
        if smallest != i:                 # one swap per round, at most
            values[i], values[smallest] = values[smallest], values[i]
    return values


print(selection_sort([29, 10, 14, 37, 12]))

#include <iostream>
#include <vector>
void selectionSort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        int smallest = i;
        // scan the unsorted suffix for the index of its minimum
        for (int j = i + 1; j < n; ++j) {
            if (values[j] < values[smallest]) smallest = j;
        }
        if (smallest != i) std::swap(values[i], values[smallest]);
    }
}
int main() {
    std::vector<int> values {
        29, 10, 14, 37, 12
    };
    selectionSort(values);
    for (int v : values) std::cout << v << ' ';
    std::cout << '\n';
}

import java.util.Arrays;
public class SelectionSort {
    static void selectionSort(int[] values) {
        int n = values.length;
        for (int i = 0; i < n - 1; i++) {
            int smallest = i;
            // scan the unsorted suffix for the index of its minimum
            for (int j = i + 1; j < n; j++) {
                if (values[j] < values[smallest]) smallest = j;
            }
            if (smallest != i) {   // one swap per round, at most
                int tmp = values[i];
                values[i] = values[smallest];
                values[smallest] = tmp;
            }
        }
    }
    public static void main(String[] args) {
        int[] values = {29, 10, 14, 37, 12};
        selectionSort(values);
        System.out.println(Arrays.toString(values));
    }
}

Watch it run

Step through it

Running on [29, 10, 14, 37, 12]

Output

On paper: Placing Each Minimum

Sorting [29, 10, 14, 37, 12] takes four rounds. The bold value is the minimum found by that round's scan.

Round 1 scan all five, find 10 at index 1, swap with index 0 → [10, 29, 14, 37, 12]
Round 2 scan [29, 14, 37, 12], find 12 at index 4, swap with index 1 → [10, 12, 14, 37, 29]
Round 3 scan [14, 37, 29], find 14 already at index 2 → no-op swap, array unchanged
Round 4 scan [37, 29], find 29, swap with index 3 → [10, 12, 14, 29, 37]
Done four rounds placed four values; the fifth is correct by elimination. 4+3+2+1 = 10 comparisons, 3 real swaps.

Notice round 3: the minimum is already in place, so the swap is a no-op — but the scan still costs a full pass. That is the cost you cannot avoid, and it is why no best case exists.

Record the minimum's index each round, then swap once
A minimum already in place still counts as a round
n−1 rounds suffice — the final element cannot be wrong
Total: 4 + 3 + 2 + 1 = 10 comparisons, 3 real swaps

The Stability Problem

Selection sort in its standard swap form is not stable. One three-element array shows exactly why — 4a and 4b are equal keys on different records:

Start [4a, 4b, 2], with 4a ahead of 4b in the input.
Round 1 the minimum is 2 at index 2. Swap it with index 0.
Result [2, 4b, 4a]. The swap carried 4a to the end, behind 4b. Original order among equals is lost.

The two 4s have exchanged places, and no later round separates them. A single long-range swap jumped a value over an equal one — that is the whole mechanism of the instability.

This is fixable: if instead of swapping you shift the intervening values right and insert the minimum, order among equals is preserved — but that turns each round's single write into up to n writes, discarding the one advantage selection sort has. In practice, when stability is required, merge sort is the answer.

A single swap can move a value across an equal key
Instability shows up whenever you sort by a second key
The shifting variant is stable but loses the O(n) swap bound
Insertion sort is stable and usually faster in practice

When to Reach for It

Selection sort is the right choice in a narrow band: small arrays where writes are expensive. Flash memory and EEPROM wear out per write, so an algorithm bounded at n−1 writes is genuinely preferable to one that might perform thousands.

It is also easy to reason about under memory pressure — O(1) space, no recursion, no auxiliary buffer, and completely predictable timing, which matters in hard real-time code where variance is worse than slowness.

Outside those cases the Θ(n²) comparison count rules it out. For general use the standard library's sort — typically quick sort with a fallback, or a merge-based stable sort — is the correct answer.

Choose it when write cost dominates read cost
Predictable, branch-light timing suits real-time constraints
Never adaptive: sorted input costs full price
For general sorting, prefer a O(n log n) algorithm

The Sorted Boundary

Why the Comparison Count Never Changes

Sort with selection sort

Step through it

On paper: Placing Each Minimum

The Stability Problem

When to Reach for It

Continue this course

Sorting Algorithms: Methods and Performance

Bubble Sort: Passes, Swaps and Complexity

Insertion Sort: Shifting, Gaps and Cost