DSABook – Selection sort

3.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 Ajvide), and put that first in the bookshelf. Then you look through the remaining pile until you find the second book (written by Bengtsdotter), and add that behind Ajvide. Then find the third book (by Cassler), and add behind Bengtsdotter. 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.

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.

Here is an implementation for Selection sort.

function selectionSort(arr):
    n = arr.size
    for i in 0 .. n-1:                  // Select 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 smaller index
        swap(arr, i, minIndex)          // Put it into place

Any algorithm can be written in 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.

3.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, $O(n^2)$ .

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, $O(n)$ .

This visualisation analyses the number of comparisons and swaps required by Selection sort.