Selection Sort

Find the next minimum

Selection sort divides the array into two parts: the left side is an already finished sorted prefix, and the right side contains the elements from which the next value must be chosen. At each step, the algorithm finds the smallest element on the right and places it at the beginning of that part.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        int tmp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = tmp;
    }
}

After the first iteration, a[0] contains the minimum of the whole array. After the second, the two smallest elements are already in the correct order, and so on. The search for the minimum itself does not modify the array: only one swap is performed at the end of each outer iteration.

How it differs from bubble sort

Bubble sort may perform many swaps during one pass, while selection sort performs at most one. However, the number of comparisons barely depends on the original order: even if the array is already sorted, the algorithm still scans the remaining part to find the minimum.

Complexity

The number of comparisons remains O(n²) in the best, average, and worst cases. Extra space is O(1). The algorithm's useful property is its small number of swaps, but on large arrays it still loses in running time to more efficient sorting algorithms.