Selection sort: find the min, swap it into position
Student can produce selection sort by composing the index-of-min loop with the three-statement swap, identify the invariant maintained by the outer loop's start index, and state the algorithm's O(n²) runtime.
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)andxs.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.
Tracing selection sort pass by pass
Student can trace selection sort on a small input array by producing a table that lists, for each outer-loop pass: the value of start, the value of minIdx after the inner loop, and the array state after the swap.
A trace is a table showing the algorithm's state at well-defined moments. For selection sort, the well-defined moments are after each outer-loop iteration. CSCD 210 midterm 2 asks students to produce this table given a starting array; the rubric awards points for showing the array state at each of those moments.
The trace format
For an input int[] xs = {5, 2, 8, 1, 9, 3}, the trace is:
| Pass | start | minIdx (after inner loop) | Array after the swap | |------|--------:|---:|---------------------| | (initial) |: |: | {5, 2, 8, 1, 9, 3} | | 0 | 0 | 3 | {1, 2, 8, 5, 9, 3} | | 1 | 1 | 1 | {1, 2, 8, 5, 9, 3} | | 2 | 2 | 5 | {1, 2, 3, 5, 9, 8} | | 3 | 3 | 3 | {1, 2, 3, 5, 9, 8} | | 4 | 4 | 5 | {1, 2, 3, 5, 8, 9} |
Six things to notice:
1. Six elements, five outer-loop passes (not six). The last slot is whatever's left; placing the second-to-last necessarily places the last as well. The outer loop runs xs.length - 1 times. 2. A minIdx equal to start means no real swap. Passes 1 and 3 are no-op iterations because the minimum of the remaining suffix is already at the front. 3. The "sorted prefix" grows by one slot per pass. After pass 0, slot 0 is finalized. After pass 1, slots 0 and 1 are finalized. Bold-underlining the sorted prefix in the trace makes the invariant visible. 4. The values 5 and 9 each move only once each across the whole trace. Selection sort is not an algorithm that nudges every element a little: each placement is final after one swap. 5. The trace ends when start reaches xs.length - 1 = 5, but the outer loop stops at start < xs.length - 1, so the last shown start is 4. The array after pass 4 is the final sorted output. 6. **The cost is the inner-loop comparisons, not the swaps.** For 6 elements the inner loop ran 5 + 4 + 3 + 2 + 1 = 15 comparison-operations across all passes. This is what O(n²) measures.
When the rubric wants a different shape
Some midterm 2 variants ask for only the array states (no start/minIdx columns); some want the inner-loop intermediate states too. Read the question. The two-column "pass / array" form is the most common.
The trace as a debugging tool
Beyond the exam, the same trace is the right tool for debugging a broken sort. Run the algorithm by hand on a 4–6 element input, write down the array after each pass, and compare against what the program prints (after inserting a System.out.println(Arrays.toString(xs)) after the swap). The first divergence is the bug's location.
In other languages
- Python: the same trace-table approach works for
sortedor any hand-rolled sort. The visualization tools (e.g.,visualgo.net) animate the trace. - Excel/Spreadsheet: the trace table fits naturally; each row is one outer pass.