Stephen Smith

Analyzing Algorithms I: Selection Sort

2023-07-23

Lately I've been re-reading Panos Louridas' Algorithms, a book I originally picked up early into web dev boot-camp and really enjoyed. Being new to programming at the time, I admit some of it went over my head. Now that I'm writing code professionally on a daily basis, I thought it would be a good idea to not only revisit Louridas' writings but also document some of my learnings. Hopefully this will help cement the concepts in my own mind and possibly even provide some helpful material for my fellow newbie programmers.

I hope to make a series of posts on this topic, so to kick it off I'm starting with something simple. I'd like to explore the inner workings of a common sorting algorithm called Selection Sort. I'll break the algorithm down with some animated examples, then we'll take a look at how to implement the algorithm and we'll calculate its time and space complexity.

Visualizing Selection Sort

I'm going to borrow the same example that Louridas uses to introduce Selection Sort in his book. However, since you, my reader, are reading this on the web; why don't we make use of some vanilla HTML and CSS animations to really help these diagrams click.

Lets first imagine an array of 10 items, each assigned a value from 1 to 10, but arranged in no particular order. Our objective is to arrange these items in ascending order.

Our initial unsorted array looks like this:

4
6
10
1
7
9
3
2
8
5

Because we are wanting to sort this array in ascending order, our Selection Sort begins by identifying the item with the lowest value in the unsorted array. Let's refer to this item as the selected item. In our case, it is the item with a value of 1. As the selected item possesses the lowest value among all the unsorted items, it rightfully belongs in the first position. Simple enough, right?

Now, we could just simply assign the selected item to the first position, but if we took this approach we'd have to shift all of the other values one space to accommodate it. Instead of re-indexing every unsorted item, a more efficient approach is to swap the selected item with the item currently in first position. All of the other items may remain untouched, and only two items require re-indexing.

First Pass

4
6
10
1
7
9
3
2
8
5

Another interesting note about the above example is how the algorithm needs to check every item in the unsorted array before making the swap. When checking index 0 (which has a value of 4) it assigns this as the lowest value, it then checks the next two items and knows that both values, 6 and 10, are not less than 4. When it reaches the fourth item, it does in fact find a value less than 4, and so index 3 (which has a value of 1) is now assigned as the lowest value.

Looking at the diagram, we know that 1 is the lowest value in the unsorted array, but the algorithm does not, and so it continues to check every index to make sure it selects the lowest value before making a swap.

Okay lets continue, so the item with the value of 1 has found its place and is now considered sorted, while the unsorted array is now one less item in length.

From here, the algorithm is basically just a repetition of everything we saw above.

Second Pass

1
6
10
4
7
9
3
2
8
5

The only notable difference here is that because the unsorted array is one item less in length, the selection process is a little bit quicker. It's not a huge difference, and we'll discuss this in more detail when we work out the time complexity.

Third Pass

1
2
10
4
7
9
3
6
8
5

In the below example, we see that the value 4 was already in its sorted position, however, the algorithm still needs to check to make sure its the lowest value before deciding to leave it in place and move on.

Fourth Pass

1
2
3
4
7
9
10
6
8
5

I'm going to save some lines of code and end our visualization on this last example, but you can take a second to imagine what the rest of the iterations look like.

Fifth Pass

1
2
3
4
7
9
10
6
8
5

Implementing Selection Sort

Now that we've visualized the main behavior of Selection Sort, let's take a look at how we might implement the algorithm in a high level language like Javascript.

First, we define the selectionSort function that takes an input array as a parameter and returns the same input array in its sorted state. Then we need to implement the outer for loop to iterate through the elements of the input array. The variable i represents the index of the current element within the array.

function selectionSort(input) {
    for (let i = 0; i < input.length; i++) {
        ...
    }
    return input;
}

We'll be sorting the input array in place, but it's helpful to mentally split it into two sub-arrays; the sorted array and the unsorted array. For each iteration, the unsorted sub-array starts at the current index i and extends to the end of the array.

Remember the ultimate goal for each iteration is to find the element of the unsorted sub-array with lowest value and swap it with index i, effectively appending it to the sorted sub-array.

Next we'll define a new variable minIndex, which we'll let be i. Then we'll iterate through the sub-array (starting at i + 1, since i is already the minIndex) and re-assign minIndex each time we find a lower value.

function selectionSort(input) {
    for (let i = 0; i < input.length; i++) {
        let minIndex = i;
        for (let j = i + 1; j < input.length; j++) {
            if (input[j] < input[minIndex]) {
                minIndex = j;
            }
        }
        ...
    }
    return input;
}

The final step is the swap, which is wrapped in an if statement that will be skipped if minIndex is equal to i (in which case index i already holds the lowest value so we can move on.)

The swap is achieved by setting a temp variable to temporarily hold the current value of input[i], while we re-assign input[i] to equal input[minIndex]. Now we can take the value of temp and assign it to input[minIndex].

function selectionSort(input) {
    for (let i = 0; i < input.length; i++) {
        let minIndex = i;
        for (let j = i + 1; j < input.length; j++) {
            if (input[j] < input[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            let temp = input[i];
            input[i] = input[minIndex];
            input[minIndex] = temp;
        }
    }
    return input;
}

And that's all there is to it. All in all, a pretty straight forward algorithm to implement.

Calculating Selection Sort's Complexity

You might've already been able to gather some of the benefits of Selection Sort.

First of all, it's relatively low in complexity. The general functionality of the algorithm can be summed up as a few simple instructions: Iterate the input array, identify the next lowest value of the unsorted items and swap it with the current index.

Also, Selection Sort doesn't take up a lot of memory. Looking at our function above, we're sorting the input array in place, and we only define a couple of extra variables (minIndex and temp). Using Big O notation we could describe Selection Sort as having O(1) space complexity. More simply put, Selection Sort takes up no more extra space than the array being sorted.

Selection Sort's weakness is its poor time complexity, which can be described as O(N^2) time complexity. Let's discuss how we find this value.

During each iteration of the outer loop, we need to find the minimum element in the unsorted sub-array, which requires traversing the entire sub-array of N elements. As a result, the time complexity of this searching operation is O(N).

After identifying the element with minimum value, we perform a constant-time swapping operation to place it in its correct position. This swapping step does not significantly impact the overall time complexity, as it takes takes O(1) time.

Throughout the N iterations of the algorithm, both the searching and swapping operations are carried out. So, the time complexity of Selection Sort becomes O(N) * O(N), or O(N^2).

In simple terms, the more items are added to the input array, the run time of selection sort will increase at a rate proportional to the square of the number of elements. This means that selection sort is okay for smaller input data sets, but not ideal for larger ones.

In Summary

By visualizing Selection Sort, walking through its implementation, and calculating its time and space complexity we can make the following conclusions:

Selection Sort...

Sorting algorithms are used in countless pieces of software that we engage with on a daily basis, and so you can imagine humans have discovered far more performant algorithms than Selection Sort.

As I'm fairly new to writing about programming I wanted to start with something like Selection Sort and work my way up in complexity. For my next algorithm blog, I think we'll discuss Merge Sort. A slightly more performant, and of course more complex sorting algorithm.

Until then, thanks for sticking around and reading this whole post. If you've got any feedback or think I may have gotten something wrong, please reach out at hello@sjsmith.dev. Also go grab a copy of Panos Louridas' Algorithms from MIT Press, I'd love to know your thoughts on the book.