Selection Sort

Selection sort says: find the smallest element, put it at the front, repeat on the rest. It’s the algorithm humans naturally invent when asked to sort a stack of papers — scan, grab the smallest, put it down, repeat.

The idea in three sentences

1. Scan the unsorted region of the array for the minimum element.
2. Swap that minimum into the first position of the unsorted region.
3. Shrink the unsorted region by one and repeat.

After n - 1 passes, everything is in place.

Watch it run

The blue “min” highlight tracks the current candidate for smallest. Each pass ends with one swap that locks in the next sorted element.

The code

void selectionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) minIdx = j;
        }
        if (minIdx != i) swap(a[i], a[minIdx]);
    }
}

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

void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
        }
    }
}

The minimum-swap claim

Selection sort does at most n - 1 swaps total — one per outer iteration, and only if the minimum wasn’t already in place. That’s the fewest of any sorting algorithm.

Why does that matter? When a swap is expensive. If you’re sorting an array of huge structs (each swap moves dozens of bytes), or sorting records on slow storage where each swap is a disk write, the cost of swapping dominates the cost of comparing. Selection sort wins.

For sorting cheap integers in memory, swap cost is negligible, and insertion sort’s better cache behavior wins easily. But for niche heavy-payload cases, selection sort is the right call.

Properties

• Time: O(n²) in all cases — best, average, worst. Never improves on sorted input.
• Space: O(1) — fully in-place.
• Stable: No, in its standard form. Swapping a far-away minimum into position can leap equal elements over each other.
• Adaptive: No.

Why it’s unstable (example)

Input:  [4a, 2, 4b, 1, 3]    (4a and 4b are equal values; subscripts mark insertion order)

Pass 1: find min = 1 at index 3. Swap with index 0.
        → [1, 2, 4b, 4a, 3]

Now 4b appears before 4a — their original order is reversed.
That's instability.

You can hack stability into selection sort by shifting the elements right instead of swapping, but at that point you’ve reinvented insertion sort.

When (if ever) to actually use it

In normal application code? Never. The two times you’d reach for it:

1. Embedded code with huge per-swap cost. When a “swap” means rewriting flash sectors or moving disk records, the O(n) swap count beats insertion sort’s O(n²) swaps.
2. As a teaching tool. The two-nested-loop structure with one swap at the end is conceptually clean.

Next up: Insertion Sort — the one O(n²) sort that actually ships inside every standard library.