Sorting Algorithms — Selection Sort

I’ve always found the best way to learn something is to teach it*. So let’s have a go at it!

A couple things to know about this algorithm:

• The time complexity runs in Quadratic Time ( Big-O: O(n²) )
• This is not the fastest or most elegant solution, but it is relatively easy to follow. (Clean & easy to read v. complicated code)
• It functions by comparing two values (a, b), and moves the lowest value to the beginning of the array.
• This version will mutate the original array, but we’ll fix this momentarily with an easy solution.

Here’s the code:

Goal: sort from least to greatest.

Process:

This array will go through the algorithm 10 times, and we’ll go through each step with the hope that this will show how the selection sort works.*

1st pass:

• i = arr[0], so the arr[i] is the first element in the array, in this array, 1. This is set on line 5.
• arr[j] and i are both 0
• minIndex = j, which is 0. This is set on line 9.
• Summary: arr[i]: 1, arr[j]: 0, arr[minIndex]: 0, arr: 1,3,0,-1,2

2nd pass:

• minIndex is 0, but gets set to -1 on line 9
• Summary: arr[i]: 1, arr[j]: -1, arr[minIndex]: -1, arr: 1,3,0,-1,2

3rd pass:

• the 2nd for loop is false, so instead a swap is initiated from line 13. This also explains why arr[j] is undefined, because it never gets there to be defined.
• [1,-1] = [-1,1]
• Summary: arr[i]: -1, arr[j]: undefined, arr[minIndex]: 1, arr: -1,3,0,1,2

4th pass:

• minIndex is 3, but gets set to 0 on line 9
• Summary: arr[i]: 3, arr[j]: 0, arr[minIndex]: 0, arr: -1,3,0,1,2

5th pass:

• the 2nd for loop is false, so instead a swap is initiated from line 13. This also explains why arr[j] is undefined, because it never gets there to be defined.
• [3,0] = [0,3]
• Summary: arr[i]: 0, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,3,1,2

6th pass:

• minIndex is 3, but gets set to 1 on line 9
• Summary: arr[i]: 3, arr[j]: 1, arr[minIndex]: 1, arr: -1,0,3,1,2

7th pass:

• the 2nd for loop is false, so instead a swap is initiated from line 13. This also explains why arr[j] is undefined, because it never gets there to be defined.
• [3,1] = [1,3]
• Summary: arr[i]: 1, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,1,3,2

8th pass:

• minIndex is 3, but gets set to 2 on line 9
• Summary: arr[i]: 3, arr[j]: 2, arr[minIndex]: 2, arr: -1,0,1,3,2

9th pass:

• the 2nd for loop is false, so instead a swap is initiated from line 13. This also explains why arr[j] is undefined, because it never gets there to be defined.
• [3,2] = [2,3]
• Summary: arr[i]: 2, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,1,2,3

10th pass:

• the two for loops return false, and this is where having the “return arr” on line 16 returns our newly sorted array.
• Summary: arr[i]: 3, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,1,2,3

Summary of the summaries:

• arr[i]: 1, arr[j]: 0, arr[minIndex]: 0, arr: 1,3,0,-1,2
• arr[i]: 1, arr[j]: -1, arr[minIndex]: -1, arr: 1,3,0,-1,2
• arr[i]: -1, arr[j]: undefined, arr[minIndex]: 1, arr: -1,3,0,1,2
• arr[i]: 3, arr[j]: 0, arr[minIndex]: 0, arr: -1,3,0,1,2
• arr[i]: 0, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,3,1,2
• arr[i]: 3, arr[j]: 1, arr[minIndex]: 1, arr: -1,0,3,1,2
• arr[i]: 1, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,1,3,2
• arr[i]: 3, arr[j]: 2, arr[minIndex]: 2, arr: -1,0,1,3,2
• arr[i]: 2, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,1,2,3
• arr[i]: 3, arr[j]: undefined, arr[minIndex]: 3, arr: -1,0,1,2,3

Summary of just the array (to see the swap happen):

As promised, we want to make this selection sort algorithm not mutate our original array. But how and why?!

We might actually need to keep the original order of the array, especially if it was previously sorted or was originally created in a specific order. Or perhaps we need to compare the sorted array to the original array

The process is simple enough by creating a “shallow copy” of the original array.

Option 1:

This method is a slightly older trick. The .slice() method, without parameters, will take all the elements, from beginning to end, of the array and make a copy.

Option 2:

Option 2 is similar to option 1, but follows more of the ES6 syntax by using the spread operator (…).

Option 3:

This method creates a whole new object in memory space. So while it’ll take up more memory, memory is cheap and I personally don’t mind that compromise. I also like this a bit more because it’s clear what is happening: we’re making a new array from “array” (or whatever array name you pass in) and we’re assigning it to “arr”.

There are tons of great visual algorithm sites. They’re amazing to watch, and very helpful. This was more to take the coding “sex appeal” out of it, and get into the code itself. Hopefully it helps because I know it helped me.

*This quote has always boggled my mind:

“Those who can, do; those who can’t, teach.”

- George Bernard Shaw

The reason being, if you can’t do the thing you’re teaching, you probably shouldn’t be teaching other people do NOT be able to do something. Obviously, if the teacher was great at some point, but maybe it’s age or a physical impairment that is limiting their ability to “do” it, then this doesn’t apply.

Consider the inverse: Albert Einstein, John Coltrane, Brendan Eich knew what they were doing and left us great lessons to continue to learn from. They “can” and “did,” but should we not learn from them?

We’ve learned great concepts and skills from brilliant people, not the people who can’t.