Basic Solutions to Sorting Algorithms: Selection Sort

This week, I’m going to continue exploring sorting algorithms by taking a closer look at a slightly lesser known algorithm, Selection Sort. If this is your first foray into sorting algorithms, Selection Sort is similar in difficulty to BubbleSort and would definitely also be great for a beginner (source: me, a beginner)! However, if you’d like to brush up a bit on BubbleSort and sorting algorithms in general, feel free to check out my guide to BubbleSort before you get started with this problem.

this gif is unrelated to my article, but pretty relevant to life right now

A Quick Note on Selection Sort

Like BubbleSort, the solution to Selection Sort also requires us to run two nested for loops. Just as I mentioned in my BubbleSort guide, these nested for loops will give Selection Sort a high worst case runtime of n². Although this runtime complexity is unideal for large datasets, Selection Sort will still work great on smaller datasets and be helpful to know if you are preparing for a technical interview!

The Solution: Our Big Assumption

I think the key to understanding this solution to Selection Sort is understanding the assumption that we will be making in our outer for loop. Basically, we are going to assume that the element at the index of i is the element with the lowest value in our array.

In case you are confused, let me break it down:

function SelectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let indexOfMin = i
  }
}

To make our assumption, we use indexOfMin, a temporary variable, and assign it to the whatever the current value of i is. Thus, as we iterate through our array, the value of indexOfMin will change with i.

The Solution: Our Big Assumption is Wrong?

Now I know what you are probably thinking, and yes, our big assumption is most likely going to be wrong. Fortunately for us, it doesn’t really matter if our assumption is eight or wrong as the job of our second, nested for loop is to prove this assumption wrong (or right, potentially).

In our inner for loop, we will check to see if there is an element with a lower value than that of the element in the array at indexOfMin. If we find a value that is lower than arr[indexOfMin], we will update the value of indexOfMin to be the value of the index of whatever element is lower.

…I feel like those last few sentences got away from me a bit, so here’s how this will look in practice:

function SelectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let indexOfMin = i
    for (let j = i+1; j < arr.length; j++) {
      if (arr[j] < arr[indexOfMin]) {
        indexOfMin = j
    }
  }
}

As you can see, in the second for loop we will check to see if the element at an index of j is less than arr[indexOfMin] and if it is we will reassign the value of indexOfMen to j (aka the index of the smaller element).

The Solution: Checking our Assumption

Now that we’ve set up our two nested for loops, we only have one last part to our solution and that is checking to see if our assumption was correct or not.

To do, we will look at the index of our current element (i) and the index of our lowest element (indexOfMin) and see if they match. If they do, we will know that our assumption was correct, but if they don’t we will know our assumption is wrong and we will have to swap the places of the two elements.

To do this, we can use a simple if statement:

if (i !== indexOfMin) {
  let smlr = arr[indexOfMin]
  arr[indexOfMin] = arr[i]
  arr[i] = smlr
}

This swapping logic is the same logic we did to swap elements in BubbleSort so if you are lost, I go over it in a bit more detail in my BubbleSort guide.

Putting It All Together

Now that we understand how all of the components of our Selection Sort solution, here is how they all work together:

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let indexOfMin = i
  
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[indexOfMin]) {
      indexOfMin = j
      }
    }
    if (i !== indexOfMin) {
      let smlr = arr[indexOfMin]
      arr[indexOfMin] = arr[i]
      arr[i] = smlr
    }
  }
  return arr
}

Hopefully, you found this walkthrough fro Selection Sort helpful and have a better understanding on how to implement a solution to this problem (or one like it!) on your own. Definitely, try to practice solving this problem (or similar ones) on your own as the best way to get better as solving algorithms is to practice!

Don’t be liz, do more than one pushup if you want to get better!