Selection sort¶

Find the smallest value and put it first. Find the smallest of the rest and put it second. Repeat.

Time (every case)	Extra space	Swaps	Stable	In place
\(O(n^2)\)	\(O(1)\)	at most \(n-1\)	no	yes

The idea¶

Think of sorting a hand of cards face up on a table: scan them all, pick out the lowest card and lay it on the left. Scan what is left, pick out the lowest again, lay it next. The left part grows by one card at a time and is always sorted and final.

Selection sort always makes the same number of comparisons, about \(n^2/2\), whatever the input looks like. Its one strength is that it makes very few writes: at most one swap per position, \(n-1\) in total.

How it works¶

For i from 0 to \(n-2\):
1. Find the position smallest of the minimum of a[i..n-1].
2. Swap a[i] and a[smallest]. Now a[0..i] is sorted and final.

Code¶

PythonJavaC++

def selection_sort(a):
    """Sorts the list a in place, smallest first."""
    n = len(a)
    for i in range(n - 1):
        smallest = i                         # find the smallest value in a[i:]
        for j in range(i + 1, n):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]  # put it at position i: a[:i+1] is now final
    return a


if __name__ == "__main__":
    print(selection_sort([64, 25, 12, 22, 11]))
    print(selection_sort([38, 27, 43, 3, 9, 82, 10]))
    print(selection_sort([2, 1]))

import java.util.Arrays;

public class SelectionSort {
    /** Sorts a in place, smallest first. */
    static void selectionSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            int smallest = i;                         // find the smallest value in a[i..n-1]
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[smallest]) smallest = j;
            int t = a[i]; a[i] = a[smallest]; a[smallest] = t;   // put it at position i
        }
    }

    public static void main(String[] args) {
        int[][] tests = {{64, 25, 12, 22, 11}, {38, 27, 43, 3, 9, 82, 10}, {2, 1}};
        for (int[] a : tests) {
            selectionSort(a);
            System.out.println(Arrays.toString(a));
        }
    }
}

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Sorts a in place, smallest first.
void selectionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int smallest = i;                            // find the smallest value in a[i..n-1]
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[smallest]) smallest = j;
        swap(a[i], a[smallest]);                     // put it at position i
    }
}

void print(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
    cout << "]\n";
}

int main() {
    vector<vector<int>> tests = {{64, 25, 12, 22, 11}, {38, 27, 43, 3, 9, 82, 10}, {2, 1}};
    for (auto& a : tests) {
        selectionSort(a);
        print(a);
    }
}

Each program prints [11, 12, 22, 25, 64], [3, 9, 10, 27, 38, 43, 82] and [1, 2].

When to use it¶

When writing is expensive. On flash memory or EEPROM, where each write wears the chip, \(n-1\) swaps beat insertion sort's up to \(n^2/2\) moves.
Tiny lists, and as a way to learn the "grow a sorted part" idea that heapsort speeds up.
Not for anything large, and not when you need stability.

Common mistakes¶

Swapping every time a smaller value is found, instead of once after the scan: still correct but does many more writes, losing the one advantage.
Expecting it to be stable. The long-distance swap can jump a value over an equal one: sorting [(2,a), (2,b), (1,c)] by number swaps (2,a) to the end, giving (1,c), (2,b), (2,a).

Going deeper¶

Each part below starts closed; open the ones you want.

Sample walkthrough: [64, 25, 12, 22, 11]

Step `i`	Unsorted part	Smallest	Swap	List after
0	`64 25 12 22 11`	11 at 4	64 ↔ 11	`[11, 25, 12, 22, 64]`
1	`25 12 22 64`	12 at 2	25 ↔ 12	`[11, 12, 25, 22, 64]`
2	`25 22 64`	22 at 3	25 ↔ 22	`[11, 12, 22, 25, 64]`
3	`25 64`	25 at 3	none needed	`[11, 12, 22, 25, 64]`

\(4 + 3 + 2 + 1 = 10\) comparisons and 3 real swaps.

The math: why it is correct and how long it takes

Invariant. Before step \(i\), \(a[0..i-1]\) holds the \(i\) smallest values in sorted order, and every value in \(a[i..n-1]\) is at least \(a[i-1]\). Step \(i\) moves the minimum of the rest to position \(i\), which keeps both statements true for \(i+1\). At the end (\(i = n-1\)) the whole array is sorted.

Comparisons are the same for every input:

\[ C(n) = \sum_{i=0}^{n-2} (n-1-i) = \frac{n(n-1)}{2} = \Theta(n^2). \]

Swaps: at most \(n-1\), one per step: \(O(n)\) writes.

How often does the "smallest so far" change? On a random order, while scanning \(m\) values the minimum changes each time we meet a new record low. The \(k\)-th value is a record with probability \(1/k\), so the expected number of changes is the harmonic number \(H_m = 1 + \tfrac12 + \cdots + \tfrac1m \approx \ln m\). Summed over all steps this is \(O(n \log n)\), small next to the \(n^2/2\) comparisons.

Watch it step by step

Blue marks the smallest value found so far, orange the value being compared, green the finished part.

Variations and related ideas

Heapsort is selection sort with a faster way to find the maximum: a heap gives it in \(O(\log n)\) instead of \(O(n)\), so the total drops to \(O(n \log n)\).
Double selection sort finds the minimum and the maximum in the same scan and places both, halving the number of passes (not the comparisons).
Stable selection sort: instead of swapping, shift the block \(a[i..s-1]\) one place right and drop the minimum in at \(i\). Stable, but now up to \(n^2/2\) moves.
Partial sort: stop after \(k\) steps to get the \(k\) smallest values in order, in \(O(kn)\).

References¶

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §5.2.3 (sorting by selection).
R. Sedgewick, K. Wayne, Algorithms, 4th ed., §2.1.