Sorting Algorithms: Selection Sort as the Most Intuitive Sorting Algorithm

Have you ever wondered how computers sort information so quickly? Suppose you gave one a list of numbers on a spreadsheet with hundreds of lines, how is it able to sort it so quickly in ascending or descending order?

In time, you’ll learn that computers are only as fast as the commands that we give them. This is especially true when it comes to sorting algorithms.

That’s right, there’s more than one.

At some point in your computer science / software engineering journey, you will come across sorting algorithms.

And having an understanding of them is absolutely essential.

In this series, we’ll go over:

• the different types of sorting algorithms (and how some are better than others)
• how to code them

Sorting Algorithm Visualization: https://www.youtube.com/watch?v=kPRA0W1kECg

The first algorithm that we’ll discuss is selection sort because it arguably is the closest to our most basic understanding of sorting.

Setting the Stage

Suppose you’re given the following list of numbers:

[5, 8, 15, 9, 3, 12]

Without code, how would you sort this?

Perhaps you first look through the entire list for the smallest number and put it aside. Then you’ll look through the list again, put aside the next smallest number, and then put it after the previous number that you selected.*

You’ll likely repeat this list until you’ve sorted the list, right?

Congrats, you just executed selection sort. Yes, it’s really that simple.

That’s great you might say. But how do we exactly put it into code?

Before we code, let’s first visual it in the following section.

*Note: You can also do this process in reverse, with the largest number.

Visualization of the Algorithm

Before writing it into code, let’s look at what our algorithm is doing.

Let’s start off with the unsorted array from earlier:

[5, 8, 15, 9, 3, 12]

We’ll also put a pointer, j, at the last position of the array to indicate the position that we’ll put the largest number.

First, we’ll scan over the array and find the largest number:

Loop 1

From this traversal, we see that 15 is the largest number.

So we’re going to put it at the end of the array by swapping 15 with 12, the value where j is pointing to.

Now our array looks like this:

[5, 8, 12, 9, 3, 15]

We’ll move our pointer one position over to the left to indicate the position that we’ll traverse the array again to find the second largest number.

Loop 2

We see that 12 is the second largest so we swap it with 3, the value that j is pointing to.

And we continue this process until the pointer j reaches the other end of the array as follows:

Loop 3

Notice how 9, the third largest number, is already in the correct position where pointer j is. We’ll technically swap 9 with 9, which is the value at position j, and continue the process.

Loop 4

Loop 5

Loop 6

We arrive at the last step where we iterate one last time over the array to find the last largest number. Since it’s 3 and position j is already there, we swap 3 with 3 and we continue.

Since j has reached the end of the array, we have completed the sorting process and ultimately have a sorted array in ascending order:

[3, 5, 8, 9, 12, 15]

The Algorithm in Code

function selectionSort(arr) {
  // pointer j starts at the end of the array
  let j = arr.length - 1;
  // loop over the array arr.length times
  for(let loopNumber = 0; loopNumber < arr.length; loopNumber++) {
    // loop until i meets j
    // every value after position j is already in correct order
    // every iteration starts at the beginning of the array
    let largestNum = arr[0];
    let largestNumIdx = 0;
    for(let i = 0; i <= j; i++) {
      // determine if the current value is the largest number so far in the iteration
      if (largestNum < arr[i]) {
        // if it is the largest number so far, replace the value and mark the index
        largestNum = arr[i];
        largestNumIdx = i;
      }
    }
    // at the end of the loop, swap the values at positions largestNumIdx with j
    let placeHolder = arr[largestNumIdx];
    arr[largestNumIdx] = arr[j];
    arr[j] = placeHolder;
    j -= 1;
  }
  // process repeats until loop ends
  return arr;
}

Runtime and Space Time Complexity

Since we’re merely manipulating the array (not always best practice), the space time is going to remain constant. Therefore, Selection Sort has a space complexity of O(1).

Should you decide to make a separate array (best practice), then it should have a space complexity of O(N), where N is the length of the unsorted array.

For runtime, notice that the number of times we needed to loop over the array is equal to the length of the array.

This is because we needed to look at almost every single value of the array multiple times to make sure they were in the correct position.

From this, we see that we have to look at each value at most N (the length of the array) times as we search for the largest number in each iteration.

Let’s look at how many times we looked at each value:

So when we add up the amount of work that we’ve done, we start to see something interesting:

1 + 2 + 3 + 4 + 5 + 6

For those that are familiar with the sum of an arithmetic series, you may remember that:

Using runtime analysis, we can see the following:

Since O(N²) is the most “dominate” speed, we can conclude that selection sort’s runtime is O(N²).

Summary

Selection sort is arguably the most intuitive way to think about sorting a list of numbers. We simply look for the largest number, put it to the end of the array, then look for the second largest number, and put it at the second to last position of the array, and so on.

However, we know from our analysis that if we were to scale this to larger lists, this process will be too slow.

In the next post, we’ll discuss bubble sort. A really popular, albeit not the best, sorting algorithm and we’ll compare the two in terms of efficiency.

If you have any thoughts on this post, your feedback is kindly welcomed.