Selection Sort

Selection sort is one of the simplest sorting algorithms out there, next to bubble sort and insertion sort. It is one of many comparison-based sorting algorithms.

Explanation

The main idea behind selection sort is to find the min (or max, depending on whether you want to sort increasingly or decreasingly) of a list of elements, and place it at the end of the left sub-list (which is made of the min/max elements of the previous iterations). The same operation is then repeated on the remaining elements, each time decreasing the list by one element (the newly found min or max), until the list is fully sorted.

Time Complexity

Best Case

If our collection of elements is already sorted in the order we want, then each time we start iterating through the elements we will find either the min or max in the beginning of the sub-list that is yet to be sorted. However, this does not change the fact that we still have to look at the rest of the list to find the min/max. Given that in every iteration the size of the sub-list with the remaining elements to look at decreases by one, we will only perform as many comparisons, meaning n + n-1 + ... + 2 + 1 which is equal to n * (n+1) / 2, resulting in an overall quadratic complexity.

Average Case

The average case would be a list of elements that is not in any particular order. Every time we look for the min, we could find it in an arbitrary position. The number of comparisons remains the same as the best case, since we still have to look at all elements. Hence the overall time complexity is also quadratic.

Worst Case

The worst case would be a collection of elements that is sorted in the “opposite” order to the one we want to sort in. For example, suppose we are sorting our list increasingly: the smallest element in a list that is sorted in decreasing order would be found one position closer in each iteration, but again this does not change the fact that we have to look at all the elements. The number of comparisons will be the same, also resulting in quadratic complexity.

Space Complexity

The only space we need is a temporary variable for when we swap the min/max to the position where it should be. This results in constant space complexity since we do not allocate anything else and only operate on the given list.

Data Structures

Selection sort is used on linear data structures, meaning lists and arrays.

Uses

Given the space and time complexity mentioned above, selection sort is best used on collections that are small in size. It is better to consider alternative sorting algorithms on large data sets, and to only use selection sort if space is a concern.

Implementation

Below is an implemetation of Selection Sort in C++ that sorts in increasing order.

void selectionSort(vector <int> & numbers) {
    for (int i = 0; i < numbers.size()-1; i++) {
        int min = i;
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers[j] < numbers[min])
                min = j;
            swap(numbers, i, min);
        }
    }
}