Selection Sort

Selection sort finds the minimum element of the unsorted suffix and swaps it into the next output position.

static void selectionSort(int[] values) {
    for (int destination = 0; destination < values.length - 1; destination++) {
        int minimum = destination;
        for (int scan = destination + 1; scan < values.length; scan++) {
            if (values[scan] < values[minimum]) minimum = scan;
        }
        int temporary = values[destination];
        values[destination] = values[minimum];
        values[minimum] = temporary;
    }
}

Before each outer iteration, the prefix before destination contains the smallest original values in sorted final positions. Selecting the minimum of the remaining suffix extends this invariant by one.

Selection sort performs n(n - 1)/2 comparisons in the best, average, and worst cases, so time is Θ(n²). It uses Θ(1) auxiliary space and at most n - 1 swaps. This ordinary implementation is not stable because a long-distance swap can move an equal-key item past another. It can be useful when writes are much more expensive than comparisons, but it is primarily pedagogical.