Sunday, 8 December 2013

Selection sort

Selection sort is an \(O(n^2)\) sorting algorithm that works by searching through a list to find the minimum element and swapping it for the first in the list. After every swap, selection sort is performed on the list with the head removed (ie. the minimum element). Due to the way that elements are swapped anywhere in the list, this is not a stable sort.

Selection sort is similar in complexity to insertion sort but almost always performs worse. This is due to the fact that selection sort has an exact number of comparisons based on \(n\), which can be defined using the arithmetic progression:

$$(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2$$

This makes its best case always contain the same amount of comparisons as its worst.

While selection sort is faster than most \(O(\log n)\) sorts for small lists, insertion sort is normally the preferable choice. It's main favourable property is that it will perform at most \(n - 1\) element swaps, so it may be useful if swapping is expensive.

Selection sort example

Comparing to heapsort

Heapsort uses the exact same technique that selection sort does in finding the minimum element and then 'detaching' the first element from the list and sorting the remainder. The only difference between them is that instead of searching for the minimum element every iteration, heapsort utilises the heap data structure to organise the sub-list and guarentee \(O(n \log n)\) run time.

Complexity

Time, worst case \(O(n^2)\)
Time, best case \(O(n^2)\)
Time, average case \(O(n^2)\)
Space, worst case \(O(1)\) auxiliary

Code

View on GitHub

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