algorithms · medium

Selection Sort

Selection sort finds the minimum of the unsorted region and swaps it into the next sorted position. It always performs about n^2/2 comparisons regardless of input, but only n-1 swaps total, which makes it attractive when writes are expensive. O(n^2) time, O(1) space, and not stable.

The code

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int m = i;                      // index of the minimum so far
        for (int j = i + 1; j < n; ++j) // scan the unsorted region
            if (a[j] < a[m])
                m = j;
        std::swap(a[i], a[m]); // move the minimum to the front
    }
}

What this lesson walks through

1. 01Selection sort — the unsorted array
2. 02Round 1: place the 1st smallest
3. 03Round 2: place the 2nd smallest
4. 04Round 3: place the 3rd smallest
5. 05Sorted

Selection sort finds the smallest element in the unsorted region and swaps it to the front. The sorted prefix grows by one each round.