Selection sort

Scan what is left for its smallest value, and swap it into the next place. Watch one swap per sweep.

⋯7void selection_sort(int *a, int n)8{9    for (int i = 0; i < n - 1; i++) {10        int m = i;11        for (int j = i + 1; j < n; j++) {12            comparisons++;13            if (a[j] < a[m])14                m = j;15        }16        if (m != i) {17            int t = a[i];18            a[i] = a[m];19            a[m] = t;20            swaps++;21        }22    }23}

The smallest of the rest

Cell 0 should hold the smallest value. Scan the whole array for it, and swap it into cell 0. Cell 1 should hold the smallest of what is left: scan cells 1 to 9, and swap. Each sweep places one value for good, and the part still to scan shrinks by one cell.

Unlike bubble sort, nothing moves during a sweep. The scan only reads; one swap at the end does all the writing.

The code and its cost

void selection_sort(int *a, int n)
{
    for (int i = 0; i < n - 1; i++) {
        int m = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++;
            if (a[j] < a[m])
                m = j;
        }
        if (m != i) {
            int t = a[i];
            a[i] = a[m];
            a[m] = t;
            swaps++;
        }
    }
}

m is the index of the smallest value seen so far in the sweep. After the inner loop it is the smallest of a[i] to a[n − 1], and the swap puts it in a[i]. The test m != i skips a swap that would exchange a cell with itself.

Counting the work

Sweep i compares a[m] with a[i + 1] to a[n − 1]: n − 1 − i comparisons. Together that is 9 + 8 + … + 1 = 45 for ten values, n(n − 1)/2 in general, for every input: the scan cannot know that the rest is sorted without looking at every value. On the house array the smallest is elsewhere at i = 0, 2, 3, 5, 6 and 8, and already in place at i = 1, 4 and 7, so selection.c prints 45 comparisons, 6 swaps.

There are at most n − 1 swaps, two writes each: at most 2(n − 1) writes to the array. That is its one strength.

Properties

Selection sort is in place. It is not adaptive: sorted input costs the same 45 comparisons. It is not stable: a swap carries a value over every cell between, and can jump it past an equal value, as the worked example shows.

Worked example

Two equal values. Sort 5a 5b 3 by value, where a and b only tell the two 5s apart. The first sweep finds 3 at cell 2 and swaps it with cell 0, which holds 5a: 3 5b 5a. The second sweep finds nothing smaller than 5b, so the order stays, and the two 5s have changed places. selection-extra.c sorts these three cards and prints 3c 5b 5a.

Writes on the house array. Selection sort writes 12 cells (6 swaps of two cells). Insertion sort, on the same array, makes 20 moves and writes each of the 9 values it inserts back once: 29 writes. Bubble sort writes 40 (20 swaps).

Two checks. How many comparisons for ten values already sorted? (45.) And how many swaps? (0, thanks to m != i.)

Where it’s used

Where writes cost more than reads. Some memories wear out with writing, or write far more slowly than they read; selection sort’s n − 1 swaps keep the writes to a minimum.

Tiny arrays, where its simple loop is enough.

A better way to find the smallest. Heapsort is selection sort with a heap to find the largest of the rest in log₂ n steps instead of a scan (Heapsort).

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.