Selection sort

In computer science, selection sort is a method for sorting data such as numbers into an ordered list. It is not an efficient method of sorting data compared to more advanced algorithms such as quicksort and heapsort. However, it is very simple to build and is usually taught to beginners in computer science.

Selection sort has a time complexity of O(n²).

Algorithm

An animation showing the selection sort algorithm in progress

When given a list of unsorted data, the algorithm will divide the list into two parts: one part that has all the sorted data and another part that has all the remaining unsorted data. When the algorithm first starts, there is no data in the first part as no data has been sorted yet and all the unsorted data is in the second part. The algorithm then starts to find the smallest item in the unsorted data and swap it with the left-most element of the list. The part with the sorted data is then the left-most element and the part with the unsorted data is the remaining unsorted elements. The algorithm repeats itself, by finding the smallest element within the list of unsorted data and swapping it with the left-most element, eventually getting a sorted data.

Here is an example of selection sort working on six elements:

Sorted part	Unsorted part	Smallest element in unsorted part
( )	(43, 91, 73, 89, 12, 20)	12
(12)	(91, 73, 89, 43, 20)	20
(12, 20)	(73, 89, 43, 91)	43
(12, 20, 43)	(89, 73, 91)	73
(12, 20, 43, 73)	(89, 91)	89
(12, 20, 43, 73, 89)	(91)	91
(12, 20, 43, 73, 89, 91)	( )

Implementation

The implementation of this algorithm requires using two nested loops. The outer loop is to work on every element in the list starting from the left-most element whereas the inner loop is to find for the smallest element within the unsorted part of the list before the smallest element is swapped with the left-most element.

A possible way of writing this algorithm in Java is shown below.

public static void selectionSort(int[] array) {
    for (int start = 0; start < array.length - 1; start++) {
        int minimumId = start;

        // Find the index of the smallest number
        for (int i = start + 1; i < array.length; i++) {
            if (array[i] < array[minimumId]) {
                minimumId = i;
            }
        }

        // Swap the smallest number with the left-most element
        int temp = array[start];
        array[start] = array[minimumId];
        array[minimumId] = temp;
    }
}

Related pages

• Bubble sort
• Insertion sort