Selection Sort

Two iterative sorting algorithms, selection sort and insertion sort, can each put an array or an ArrayList in order. Iterative means each is built from loops. This lesson is about selection sort.
The passes
The array below holds five seedling heights, sorted here into increasing order.
int[] heights = {68, 31, 54, 22, 47};
for (int start = 0; start < heights.length - 1; start++)
{
    int smallest = start;
    for (int k = start + 1; k < heights.length; k++)
    {
        if (heights[k] < heights[smallest])
        {
            smallest = k;
        }
    }
    int held = heights[start];
    heights[start] = heights[smallest];
    heights[smallest] = held;
}
On every outer pass, the inner loop locates the lowest height from start to the end, and the swap puts it at position start. The table shows the array after each pass, with the sorted portion growing from the left.
After pass01234
before6831542247
12231546847
22231546847
32231476854
42231475468
Pass 1 finds 22 at index 3 and swaps it with the 68. Pass 2 looks at indexes 1 through 4, where the lowest height, 31, is already at index 1. So the swap exchanges index 1 with itself, and the array doesn't change. Pass 3 swaps 47 into index 2, and pass 4 swaps 54 into index 3.
Five elements need four passes. Once the first four positions hold the four smallest values, the last position can only hold the largest.
Final positions
After k passes, the first k positions hold the k smallest values, in the places they'll keep. A later pass never changes them, since it searches only the positions after them. The values behind them have no such guarantee: the 68 sits at index 3 after pass 1 and ends at index 4.
The inner loop finds a position and leaves the values alone. It compares each element with heights[smallest], the smallest one found so far, and only after the loop does the swap happen. The swap needs held, since the first assignment overwrites the value at start.
Counting the work
Pass 1 compares 4 pairs, pass 2 compares 3, pass 3 compares 2, and pass 4 compares 1, for 10 comparisons in all. The count depends only on the length. An array of five values that's already sorted gets the same 10 comparisons and the same four swaps. Nothing in the method checks whether it could stop early.
A version that picks the largest value instead puts it at the back, so the sorted part grows from the right.