Selection Sort

The idea

Imagine lining up students by height. You scan the whole group, find the shortest student, and put them first. Then you scan the rest, find the next shortest, and put them second. You keep going until everyone is in place.

Selection sort does exactly this:

1. Look at the unsorted part of the array and select the smallest value.
2. Swap it with the first element of the unsorted part.
3. That position is now final, so the sorted part grows by one.
4. Repeat until the unsorted part has only one element left.

In the 3D model, the pink min tag jumps every time a smaller value is found. At the end of each pass, one long swap puts the minimum into its final green position.

Step by step example

Sorting [64, 25, 12, 22, 11]:

Four passes, 4 + 3 + 2 + 1 = 10 comparisons and only 3 swaps.

Code

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i                          # index of the smallest so far
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]        # one swap per pass
    return a

print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]

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

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

int main() {
    vector<int> a = {64, 25, 12, 22, 11};
    selectionSort(a);
    for (int x : a) cout << x << " ";   // 11 12 22 25 64
}

Analysis

• Comparisons: pass 1 checks n − 1 values, pass 2 checks n − 2, and so on: (n−1) + (n−2) + … + 1 = n(n−1)/2. This number does not depend on the input, so the best, average and worst cases are all O(n²).
• Swaps: at most one per pass, so at most n − 1. This is the smallest number of writes of any simple sort.
• Space: O(1), because it sorts in place.

Why it is not stable

A stable sort keeps equal values in their original order. Selection sort’s long swap can break that. In [4a, 4b, 1], the first pass swaps 4a with 1, giving [1, 4b, 4a], and now 4b comes before 4a. (A stable version exists, but it shifts elements like insertion sort and loses the “few writes” advantage.)

Selection vs bubble vs insertion sort

Where is it used?

• When writing is expensive but reading is cheap, for example flash memory that wears out with every write. Few swaps means few writes.
• For very small arrays, where its simple code is good enough.
• As an idea: heap sort is selection sort with a heap that finds the minimum (or maximum) in O(log n) instead of O(n), which brings the total down to O(n log n).

Common mistakes

• Swapping inside the inner loop every time a smaller value is found. That still sorts, but it makes many swaps and is no longer selection sort.
• Remembering the value of the minimum instead of its index. You need the index to swap.
• Starting the inner loop at j = i instead of j = i + 1. It works, but adds a useless comparison every pass.
• Thinking selection sort gets faster on sorted input. It does not, because the scan always runs to the end.