Selection sort

Selection sort: find the min, swap it into position

Selection sort sorts an array in place by repeatedly finding the smallest remaining element and swapping it into the next "sorted" slot. The skeleton composes two patterns the course has already taught: the index-of-min variant of the best-so-far pattern, and the three-statement swap through a temporary variable.

public static void selectionSort(final int[] xs) {
    for (int start = 0; start < xs.length - 1; start++) {
        int minIdx = start;
        for (int i = start + 1; i < xs.length; i++) {
            if (xs[i] < xs[minIdx]) {
                minIdx = i;
            }
        }
        // swap xs[start] and xs[minIdx]
        final int temp = xs[start];
        xs[start] = xs[minIdx];
        xs[minIdx] = temp;
    }
}

Three structural commitments:

1. The outer loop's start is "where the next-smallest goes." On iteration 0, start is 0; the inner loop finds the minimum of the whole array and the swap moves it to position 0. On iteration 1, start is 1; the inner loop ignores position 0 (which already holds the minimum) and finds the minimum of xs[1..length-1]. The invariant: after the outer loop's k-th iteration completes, xs[0..k] is sorted and contains the k+1 smallest values. 2. The inner loop starts at start + 1, not 0. Comparing every iteration to the entire array would still produce a correct sort but would do redundant work: the slots [0..start) are already in their final positions. Skipping them is the algorithmic win that distinguishes selection sort from a naive "repeatedly sort the whole array" attempt. 3. The outer loop stops at xs.length - 1, not xs.length. Once xs.length - 1 slots are in place, the last slot necessarily holds the largest remaining value. A final iteration would compare it to itself; harmless but redundant.

Runtime

The inner loop runs n - 1, then n - 2, then n - 3, … iterations across the outer loop's lifetime. The total is n(n-1)/2, which is O(n²). Doubling the array size quadruples the runtime. Selection sort is asymptotically slower than the O(n log n) algorithms in java.util.Arrays.sort (which uses a tuned quicksort/mergesort hybrid), but its simplicity makes it the canonical first-sort to teach. CSCD 210 students implement it from scratch; production code uses Arrays.sort.

When to choose minIdx over min

The min value alone is enough to find the minimum, but selection sort needs the index of the minimum so the swap knows which slot to take from. Tracking minIdx lets the inner loop's if compare via xs[i] < xs[minIdx]: two array reads per iteration. The min-value variant int min = xs[start]; if (xs[i] < min) { min = xs[i]; minIdx = i; } is equivalent but doubles the bookkeeping.

In other languages

• C: identical algorithm; the index-tracking pattern is universal.
• Python: sorted(xs) and xs.sort() are built-ins (Timsort, O(n log n)); the selection-sort form is a teaching exercise only.
• Java standard: Arrays.sort(int[]) (dual-pivot quicksort), Collections.sort(List<E>) (Timsort). Use these in production; never ship a hand-written selection sort.