Selection sort

Selection sort repeatedly finds the smallest unsorted element and swaps it into its correct position. After each pass, one more element is locked into place at the start of the array.

The algorithm:

1. Start at the beginning. Find the smallest element in the array.
2. Swap it with the first element.
3. Now the first position is sorted; the rest is unsorted.
4. Find the smallest element in the remaining unsorted portion. Swap with the second element.
5. Repeat until the entire array is sorted.

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        swap(&arr[i], &arr[minIdx]);
    }
}

Big O

• Best case: $O(n^2)$. Even an already-sorted input requires $O(n^2)$ comparisons because the algorithm doesn’t know when to stop early — it always scans the rest of the array for each position.
• Average case: $O(n^2)$.
• Worst case: $O(n^2)$.

The number of comparisons is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$ regardless of input.

The number of swaps is exactly $n-1$ — one per outer iteration. This is one of selection sort’s saving graces: minimal swaps. If swapping is expensive (e.g., moving large records), this matters.

When to use it

Almost never, in serious code. Selection sort is mostly a teaching tool. Practical sorts (quicksort, merge sort, heap sort) all run in $O(n\log n)$, which beats $O(n^2)$ for any non-trivial input size.

The one place selection-style ideas survive: partial sorting (find the K smallest items), where modified selection beats fully sorting just to take the first K.

Vs other O(n²) sorts

Sort	Comparisons	Swaps	Stable?
Selection	$n(n-1)/2$	$n-1$	No
Bubble	up to $n(n-1)/2$	up to $n(n-1)/2$	Yes
Insertion	up to $n(n-1)/2$	up to $n(n-1)/2$	Yes

Selection makes the fewest swaps but doesn’t preserve relative order of equal elements (not stable). Bubble sort and insertion sort are both stable.

A subtlety: the array form of selection sort shown above is not stable, because swapping arr[i] with arr[minIdx] jumps a possibly-different element over the elements between them, scrambling their order relative to equal keys. A linked-list version that moves the minimum node to the sorted prefix (rather than swapping values) is stable, because moving doesn’t disturb the order of the elements left behind. This is one of the few cases where a linked-list reimplementation changes the algorithm’s stability.

For the related sort that uses a heap (much faster), see Heap sort. For more efficient general-purpose sorts, see Quick sort and Merge sort.