Selection Sort — Algorithms & DS

Bubble sort makes O(n²) swaps — it swaps adjacent pairs all the way across. Selection sort asks: what if we only swap when we've found the smallest remaining element? Same asymptotic complexity, but exactly n−1 swaps total regardless of input. When a write is expensive — flash memory, a slow device — that difference matters.

How it works

Selection sort divides the array into a sorted left portion and an unsorted right portion. Each pass scans the unsorted portion, finds the minimum, and swaps it to the boundary. The boundary advances one step right. Repeat until the array is sorted.

c

void selection_sort(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx]) min_idx = j;

        // swap arr[i] and arr[min_idx]
        int tmp      = arr[i];
        arr[i]       = arr[min_idx];
        arr[min_idx] = tmp;
    }
}
          

Tracing through an example

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

pass	array state	action
start	[64, 25, 12, 22, 11]	—
1	11, [25, 12, 22, 64]	min=11 at idx 4, swap with idx 0
2	11, 12, [25, 22, 64]	min=12 at idx 2, swap with idx 1
3	11, 12, 22, [25, 64]	min=22 at idx 3, swap with idx 2
4	11, 12, 22, 25, [64]	min=25 at idx 3, already in place
done	11, 12, 22, 25, 64	4 swaps total (n−1)

Comparisons vs swaps

Selection sort always makes Θ(n²) comparisons regardless of input order — it scans the entire unsorted portion every pass. But it makes at most n−1 swaps, because each pass does exactly one swap.

Bubble sort can make O(n²) swaps in the worst case (every adjacent pair out of order). When writes are significantly more expensive than reads — flash memory, slow I/O — selection sort's fixed swap count matters.

💡

Selection sort is not stable. A sort is stable if equal elements maintain their original relative order. The swap in selection sort can move an element past an equal one. Bubble sort and insertion sort are stable; selection sort is not.

one-line takeaway

Selection sort does exactly n−1 swaps — making it preferable to bubble sort when writes are costly.