Selection Sort Algorithm

The smallest unsorted value belongs at the boundary

Selection sort grows a sorted prefix from left to right. At boundary index 0, the whole array [29a, 10, 14, 29b, 13] is still available, so the smallest value, 10, belongs at index 0. After that pass, index 0 is permanent. The next boundary is index 1, and only the suffix [29a, 14, 29b, 13] needs to be searched for its smallest value, 13.

The outer loop chooses the boundary. The inner loop scans the unsorted suffix and remembers where its smallest value is. When the scan finishes, the value at that remembered index is swapped with the boundary value. The scan does not change the array, so each pass has one clear decision: which remaining value belongs at the boundary?

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

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

    if (minIndex != boundary) {
        swap(arr[boundary], arr[minIndex]);
    }
}

Finding a minimum changes an index, not the array

On the first outer-loop pass, the boundary is index 0 and minIndex starts at 0. The scan compares index 1, containing 10, with index 0, containing 29a. Since 10 is smaller, minIndex changes to 1. The scan then checks 14, 29b, and 13. None is smaller than 10, so minIndex stays at 1.

Only after the inner scan ends does the swap happen. The value at minIndex 1, which is 10, exchanges places with the value at boundary index 0, which is 29a. The array becomes [10, 29a, 14, 29b, 13]. Index 0 is now the first part of the sorted prefix, and the remaining values form the unsorted suffix.

One completed pass makes one more position permanent

The second pass starts at boundary index 1. Its unsorted suffix is [29a, 14, 29b, 13]. The minimum is 13 at index 4, so swapping it with the value at index 1 produces [10, 13, 14, 29b, 29a]. Indices 0 and 1 now contain the two smallest values in ascending order.

The third pass starts at index 2. The suffix is [14, 29b, 29a], and 14 is already its smallest value, so minIndex remains 2 and no value-changing swap is needed. The fourth pass checks [29b, 29a]. Their numeric values are equal, so the first equal value remains the minimum and the array stays [10, 13, 14, 29b, 29a].

The invariant is that every position before the boundary is sorted and contains the smallest values in the whole array. A pass preserves this invariant because it puts the smallest value from the unsorted suffix at the boundary, immediately after the already-correct prefix. Later passes never need to revisit earlier positions, because changing one of them would break the invariant.

Selection sort does the same number of comparisons on every ordering

For n = 5, the first inner loop compares four pairs of values, the second compares three, the third compares two, and the fourth compares one. The total is 4 + 3 + 2 + 1 = 10 value comparisons. This count depends on the array length, not on whether the values are already ordered or badly ordered.

The outer loop and inner loop together give selection sort O(n^2) time, because the number of comparisons is (n - 1) + (n - 2) + ... + 1. The algorithm uses O(1) extra space: it needs only variables such as boundary, minIndex, and j. It is in-place because it rearranges the array itself rather than creating another array.

There are at most n - 1 value-changing swaps, one after each non-final boundary. If minIndex equals the boundary, skipping the self-swap avoids counting an operation that changes no value. In this trace, only the first two passes change values, so there are two value-changing swaps despite the 10 comparisons.

for (int j = boundary + 1; j < n; j++) {
    if (arr[j] < arr[minIndex]) {
        minIndex = j;
        swap(arr[boundary], arr[j]);
    }
}

Equal values can leave in a different relative order

The labels 29a and 29b show that the two equal numeric values started in the order 29a, then 29b. On the second pass, 13 at index 4 swaps with 29a at index 1. That moves 29a to index 4, after 29b, producing [10, 13, 14, 29b, 29a].

The numeric values are sorted, but the relative order of equal values has changed. That makes the usual swap-based selection sort unstable. Stability would require equal values to keep their original order, so an algorithm that swaps a later minimum across an equal earlier value cannot promise that property.