Selection sort

›Short versionOpen if you only have a minute.

Each step scans the unsorted suffix, finds the minimum, and swaps it into the next position of a growing sorted prefix.
The usual swap makes the sort unstable. An earlier equal key can leap over a later one.
Extra memory is a few indices. The sort is in-place.
Every input costs about n² / 2 comparisons. Sorted data does not reduce that scan. The number of swaps stays about n.
Application code calls Arrays.sort. Objects go through Timsort, which is stable. Primitive arrays go through a dual-pivot quicksort.

The prefix is finished

At the start of index i, every slot before i already holds the smallest values, in order. The inner loop only reads i through the end. It remembers the index of the minimum and swaps that element with arr[i]. One swap extends the finished prefix by one.

On [29, 10, 14, 37] the first scan finds 10 and swaps it with 29. The second scan finds 14 in the suffix and swaps it with 29. The last two positions are already in order, and the loop still confirms that by scanning them.

Unstable, in-place, always quadratic

This version is . Take records [4a, 4b, 1]. The minimum is 1, so it swaps with 4a and the array becomes [1, 4b, 4a]. The two equal keys have changed order. The inner test uses <, so a later equal minimum would stay put, and that detail does not repair the leap caused by the swap.

The sort is . Time does not improve on friendly input. The suffix scan always runs to the end, so best, average, and worst case are all about n² / 2 comparisons.

Selection sort runs on [4a, 4b, 1]. After the first swap, where is 4a?

At the end. The minimum is 1, and it swaps with the occupant of index 0, which is 4a. The array is [1, 4b, 4a]. 4a has moved past 4b, so this sort is unstable.

When the library sort takes over

Call Arrays.sort for application data. An object array is sorted with . An int[] is sorted with the JDK dual-pivot quicksort. Either call removes the quadratic scan. Selection sort remains a clear picture of a growing sorted prefix, and of how a single distant swap disturbs equal keys.

SelectionSort.java

public class SelectionSort {
    static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        sort(arr);
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}