Selection Sort

Sorting O(n²) O(1)

Scans the unsorted part for the smallest element and swaps it into the next position of the sorted prefix.

Idle

Starting Selection Sort on 8 elements.

InvariantA[0..0-1] is sorted and holds the 0 smallest values — they will never move again.

1/54

comparisons0swaps0i0j0min0

compareswapshiftselectsorted

selection-sort.c

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) min = j;
        }
        if (min != i) {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}

How Selection Sort works

Scan the unsorted part for its minimum and swap it into the next slot of the sorted prefix. The prefix grows one element per pass, and each element is moved at most once.

Best case

No best case — it always scans the full unsorted part: O(n²) comparisons even when sorted.

Worst case

Same O(n²) comparisons, but never more than n−1 swaps in total.

When to use it

When writes are expensive (e.g. flash memory) — it minimizes the number of swaps.