Selection Sort Places One Minimum at a Time

A pass must finish searching before it swaps

Selection sort divides the array into a sorted prefix and an unsorted suffix. At the start, the sorted prefix is empty, so the whole array [29, 18, 7, 14, 3] is the unsorted suffix. The first pass must find the smallest value in that entire suffix before it places anything at index 0.

Set minIndex to 0, because 29 is the first candidate for the minimum. Compare each later value with the value at minIndex. Finding 18 changes minIndex to 1, finding 7 changes it to 2, and finding 14 changes nothing because 14 is not smaller than 7. The final value, 3, changes minIndex to 4.

Only after the scan reaches the end does the swap happen. The value at index 4, 3, moves to index 0, and 29 moves to index 4. The array becomes [3, 18, 7, 14, 29]. A comparison changes minIndex, not the array. Swapping as soon as you see 18, then 7, then 3 would describe a different algorithm and would lose the selected position before the scan is complete.

Each completed pass makes one more position final

After pass 0, index 0 contains the smallest value in the whole array, so [3] is the sorted prefix and [18, 7, 14, 29] is the unsorted suffix. Pass 1 searches only that suffix. It selects 7 at index 2 and swaps it with the value at index 1, producing [3, 7, 18, 14, 29]. The sorted prefix has grown to [3, 7].

Pass 2 searches [18, 14, 29]. Its minimum is 14 at index 3, so swapping indices 2 and 3 produces [3, 7, 14, 18, 29]. The sorted prefix is now [3, 7, 14]. Pass 3 searches [18, 29]. The minimum is already at index 3, so the array stays [3, 7, 14, 18, 29].

The invariant is that every value in the sorted prefix is no greater than every value in the remaining unsorted suffix. A pass preserves this invariant because it chooses the minimum value from the suffix and puts it at that suffix's first position. Once indices 0 through 3 are final, the value at index 4 is forced to be the last remaining value.

The shrinking suffix determines both loop bounds

The outer index i marks the first position of the unsorted suffix. It starts at 0 and moves through n - 2, because the final remaining position needs no search. For each i, set minIndex to i, then let the inner index j scan from i + 1 through n - 1. The inner loop compares every later value with the current minimum.

void selectionSort(vector<int>& a) {
    int n = a.size();

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex != i) {
            swap(a[i], a[minIndex]);
        }
    }
}

static void selectionSort(int[] a) {
    int n = a.length;

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex != i) {
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

The condition minIndex != i skips a physical swap when the first value in the suffix is already its minimum. For [29, 18, 7, 14, 3], that happens on pass 3, when index 3 already holds 18. Skipping that swap does not change the result, but it avoids unnecessary data movement.

for (int i = 0; i < ___; i++)

Selection sort limits swaps but not comparisons

For five values, the inner loop makes 4 comparisons on pass 0, then 3, then 2, then 1. The total is 4 + 3 + 2 + 1 = 10 comparisons. This count does not depend on the value order, because every pass still scans its entire unsorted suffix before it can know which value is smallest.

The running array performs three data-moving swaps: indices 0 and 4 on pass 0, indices 1 and 2 on pass 1, and indices 2 and 3 on pass 2. Pass 3 finds minIndex equal to i and skips the physical swap. In general, selection sort performs at most n - 1 data-moving swaps, because there are only n - 1 passes and each pass performs at most one swap.

The number of comparisons grows quadratically: (n - 1) + (n - 2) + ... + 1, which is O(n^2) time. The array itself is rearranged in place, and the algorithm stores only variables such as i, j, and minIndex, so its extra space is O(1). Fewer swaps do not make the algorithm linear, because the full suffix scan still happens on every pass.