Selection Sort in C: Program, Passes and Stability Caveat

Selection sort in C repeatedly finds the smallest value in the unsorted suffix and swaps it into the next output position. Unlike insertion sort, it selects a minimum rather than shifting a key into a sorted prefix. Its comparison count is quadratic even when the input is already sorted, but it performs at most n − 1 nontrivial swaps.

Complete selection-sort program

At the start of pass i, positions before i hold the smallest values in sorted order. The inner loop finds the minimum position from i through the last element. Only then does the program swap.

#include <stdio.h>
#include <stddef.h>

void selection_sort(int values[], size_t count) {
    for (size_t i = 0; i < count; ++i) {
        size_t smallest = i;
        for (size_t j = i + 1; j < count; ++j) {
            if (values[j] < values[smallest]) smallest = j;
        }
        if (smallest != i) {
            int temporary = values[i];
            values[i] = values[smallest];
            values[smallest] = temporary;
        }
    }
}

int main(void) {
    int values[] = {64, 34, 25, 12, 22};
    size_t count = sizeof values / sizeof values[0];
    selection_sort(values, count);
    for (size_t i = 0; i < count; ++i) {
        printf("%s%d", i == 0 ? "" : " ", values[i]);
    }
    putchar('\n');
    return 0;
}

12 22 25 34 64

Dry run: selection versus insertion

On the first pass, all remaining candidates must be examined before deciding that 12 is the smallest. Updating smallest stores an index, not the value itself. Swapping immediately every time a smaller candidate is found is a different algorithm and loses the low-swap property of this version.

Insertion sort, by contrast, takes the next unsorted value, shifts larger prefix values and inserts that key. Both build a sorted prefix, but they do different work and have different best cases.

Complexity and why it is not stable

The comparisons total (n − 1) + (n − 2) + ... + 1, or n(n − 1)/2, regardless of initial order. Best, average and worst time are all O(n²). Extra storage is O(1). The final singleton pass makes no comparison and no swap.

The usual swapping algorithm is not stable. Imagine labeled records 2a 2b 1. Swapping the first 2 with 1 produces 1 2b 2a, reversing the two equal keys even though the comparison is strict. The labels track identity; they are not C integer syntax. A stable selection variant can shift elements instead of making a distant swap, but that is not the program shown here.

Selection sort's small number of swaps may be useful when writes are expensive, but its many comparisons still make it a poor default for large arrays. See heap sort for an in-place O(n log n) worst-case alternative and merge sort when stable merging is important.

Array contract and tests to try

The function modifies count writable integers in place. The caller supplies the length; sizeof can calculate that length in main, where values is an array, but not from an array parameter, which adjusts to a pointer. With count zero the function touches nothing and permits a null pointer; positive counts require a valid array. Do not create a nonstandard zero-length array to test empty input.

No stdin is needed. Edit the initializer and run again: {3, -1, 3, 0} should become -1 0 3 3; {2, 2, 2} stays unchanged. Also test one element, ascending order, reverse order and integer extremes. The comparisons do not subtract two integers, so they do not introduce signed overflow when comparing INT_MIN with INT_MAX.

The expected output is a reference, not a fresh compiler execution. The run link loads the exact displayed program and clears old stdin. See arrays for indexing and program structure for the role of headers, functions and main.

Practice and common mistakes

Trace {3, 1, 2, 1}. The first two completed passes give 1 3 2 1 and 1 1 2 3; later passes make no swaps. For descending order, select the largest suffix value instead. Do not reset smallest to 0 on every pass: it must start at i so the sorted prefix is left alone.

Check the sorting comparison table before choosing an algorithm. “Fewer swaps” and “faster overall” are not equivalent claims.

Frequently asked questions

Does selection sort stop early on sorted data?

Not this standard version. It still scans the suffix each pass to establish the minimum, so its best-case comparison count is quadratic.

Is selection sort stable if the comparison uses less-than?

No. A distant swap can move an equal-key record past another one without directly comparing them. Stability needs a different movement strategy.