2.5 Selection sort
Let’s say you have a large pile of books that you want to put in your bookshelf, in alphabetical order by author’s surname. How would you go about? One natural way to do handle this is to look through the pile until you find the first book (say, by an author named Alakoski), and put that first in the bookshelf. Then you look through the remaining pile until you find the second book (written by Beskow), and add that behind Alakoski. Then find the third book (by Carlberg), and add behind Beskow. Proceed through the shrinking pile of books to select the next one in order until you are done. This is the inspiration for our next sorting algorithm, called Selection sort.
In the description above the books are not in the shelf from the start, which makes the algorithm not in-place. But it is easy to turn this into an in-place algorithm, where all books are in the shelf from the start. We just have to remember an invisible separator between the sorted books (on the left) and the still-unsorted books (on the right). Whenever we have found the next book to put in place, we swap it with the book that is in the way.
Algorithm: Selection sort
Divide the array into a sorted and an unsorted part, the sorted part is to the left and initially empty. Then repeat the following until the unsorted part is empty:
- Find the smallest unsorted element, e.
- Swap e with the leftmost of the unsorted elements.
- Now e will belong to the sorted part, and the unsorted part has decreased by one.
The i’th pass of Selection sort “selects” the i’th smallest element in the array, placing it at position i in the array. In other words, Selection sort first finds the smallest element in an unsorted list, then the next smallest, and so on. Its unique feature is that there are few swaps, much fewer than Bubble sort. To find the next-smallest element we have to search through the entire unsorted portion of the array, but only one swap is required to put the element into place. The algorithm above can be implemented as follows in pseudocode:
selectionSort(arr):
n = arr.size
for i in 0 .. n-1: // Select the i'th smallest element:
minIndex = i // Current smallest index
for j in i+1 .. n-1: // Find the smallest value:
if arr[j] < arr[minIndex]: // Found something smaller:
minIndex = j // Remember the smaller index
swap(arr, i, minIndex) // Put the smallest value into place
Figure 2.1 illustrates two steps of this algorithm. Note how the initial part of the array, below index i, is sorted. Also, the largest value before i is smaller than all subsequent values. Because we always select the smallest remaining value for the next position, both these properties are preserved at each step, and the end result is that the whole array is sorted.
Like any algorithm, Selection sort can be implemented in several slightly different ways. For example, we could have written Selection sort to find the largest element and put it at the end of the array, then the next smallest, and so on. That version of Selection sort would behave very similar to our Bubble sort implementation, except that rather than repeatedly swapping adjacent values to get the next-largest element into place, it instead remembers the position of the element to be selected and does one swap at the end.
Selection sort visualisation
Consider the example of the following array.
Now we continue with the second pass.
However, since the smallest element is already at the beginning, we will not need to look at it again.
Selection sort continues in this way until the entire array is sorted.
The following visualisation puts it all together. You can input your
own data if you like.
Now try for yourself to see if you understand how Selection sort
works.
2.5.1 Selection sort analysis
We have a nested for loop, where the inner loop depends on the loop variable of the outer loop.
- The outer loop is iterated n times in total.
- In iteration i, the number of comparisons made by the inner loop is always n-i-1.
As you might notice, this is exactly the same as the number of comparisons Bubble sort makes. So, Selection sort makes n(n-1)/2 comparisons, which is quadratic.
The advantage compared to Bubble sort is that Selection sort makes a lot fewer swaps. For each outer iteration it only makes one swap, so the total number of swaps will be n-1 (we get the last element in place “for free”). So, Selection sort makes a linear number of swaps, meaning that it grows linearly with the size of the array.