Selection sort

Written Explanation

The idea

For {29, 10, 14, 37, 13}:

1. The whole array is unsorted. The smallest value is 10 (at index 1). Swap it with the value at index 0. Now {10, 29, 14, 37, 13}, and position 0 is final.
2. From index 1 on, the smallest is 13 (at index 4). Swap it with index 1. Now {10, 13, 14, 37, 29}.
3. From index 2 on, the smallest is 14 (already at index 2). It stays.
4. From index 3 on, the smallest is 29 (at index 4). Swap with index 3. Now {10, 13, 14, 29, 37}.
5. One element is left and it must be the largest, so we stop.

Each pass fixes one position for good. A position in the sorted part never changes again.

The code

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) min = j;
        }
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

How to read it:

• i is the first position of the unsorted part. Everything before i is sorted and final.
• min holds the index of the smallest value seen so far. It starts as i (assume the first one is the smallest).
• The inner loop checks every later position j. If a[j] is smaller than the current smallest, min becomes j.
• After the inner loop, min is the index of the smallest value in the unsorted part. One swap puts it at position i.

Why remember the index and not the value? Because we need to know where to swap from. If we kept only the value, we could not find its position again without another search.

The outer loop stops before the last element (i < a.length - 1). When only one element remains, it is already the largest and already in place.

Tracing it

A version that prints after each pass shows the process on the example:

pass 1: smallest 10 at 1, [10, 29, 14, 37, 13]
pass 2: smallest 13 at 4, [10, 13, 14, 37, 29]
pass 3: smallest 14 at 2, [10, 13, 14, 37, 29]
pass 4: smallest 29 at 4, [10, 13, 14, 29, 37]

Pass 3 shows a detail: the smallest was already in the right place (min == i), so the swap exchanged the element with itself and nothing changed. The code swaps anyway. It is simpler, and it costs almost nothing.

Counting the work

Selection sort always scans the whole unsorted part to be sure it found the smallest. So:

• Comparisons: n - 1, then n - 2, down to 1, the same total as bubble sort: 10 for 5 elements and 780 for 40. This number does not depend on the data. An already sorted array costs exactly as many comparisons as a reversed one, and there is no early exit.
• Swaps: exactly one per pass, so n - 1 at most (some of them swap an element with itself). Bubble sort could make many more swaps on a reversed array: 10 for the reversed 5-element array, against 4 for selection sort.

Both algorithms grow like n × n in comparisons, so for large arrays both are slow. If swapping is expensive (writing to slow storage, for example), selection sort's low swap count can matter. For plain int values it usually does not.