Selection Sort Algorithm
In my previous blog post, I discussed one of the more elementary algorithms, the classic bubble sort algorithm. It’s great to learn these algorithms and bounce off of each other because you run into many similarities and are able to really visualize what is happening when you can compare the under-the-hood functionality of these algorithms. Today, I’m going to be going over another sorting algorithm, which happens to be the opposite of bubble sort.
Just to recap, bubble sort sorts our elements one by one at the end (sorting the largest integers first). On the other hand, we have selection sort. Selection sort takes the minimum element (or smallest integer in the array) and puts the smallest value into its sorted position at the beginning of the array. So, selection sort begins the sorting from the beginning and works its way sorting each number out until you reach the end of the array. In both bubble sort and selection sort algorithms, we are still moving from the beginning of the array to the end but for selection sort the actual sorted data is accumulating at the beginning.
Break it down
It’s beneficial to first think out logically how your brain would perform each step in order to understand the code base you want to achieve. The way selection sort performs is that you start at the beginning of the array and go all the way through the array, comparing each value and looking for the smallest value. Once you find the minimum value, you place it at the front of the array (the element furthest to the left). Selection sort is similar to bubble sort since it uses the swapping method as well. We want to swap the number in that first position with the lowest number.
Let’s say we are given this array: [8,5,7,2,6]. We will start at 8 and compare it with the number next to it, 5. Which one is the smallest? 5 < 8 so now 5 is our minimum… for now. But then we compare our minimum, which is 5, to the next number 7. It is still lower. We continue to go down the line and compare 5 to 2. Since 2 is less than 5, we set 2 to be our new minimum. And then we compare 2 to 6. Now that we hit the end, we have to perform our swap. We take whatever the minimum element was, which is 2, and whatever we started with, 8, and swap their indexes. So, our array after one iteration will look like this: [2, 5, 7, 8, 6]. Compared to bubble sort where we are pushing the largest element to the end. Selection sort is doing the opposite and building the smallest numbers in the correct order first.
Steps needed in the function
You want to create a variable to store your minimum value in. When you initially begin going through your array, the minimum number will just be the first element since it’s the first thing you are seeing. Then, as we go through, you will compare this value to the next until you find the smallest number. If that next number is smaller, you update that item to be the minimum variable. If not, we continue to going. At any point if there is a smaller item, we replace the minimum value with that item. When we are saving to the minimum variable, we are saving the index of where that value is found so we just swap it. All we are focusing on is swapping the position of two items. After one loop, we know that the first item is already sorted so we don’t have to loop over every single item. We know we are able to start at the next element after that one we placed in a specific index location. And then we repeat the process again. If we kept looking at the same entire array every time, we would always have the same minimum since the lowest number in the array will not change. This is why we are focusing on the next subset of numbers from within that array. So it will go from [8,5,7,2,6] to [2,5,7,8,6] to ignoring the 2 and focusing on the smallest in this subset [5,7,8,6], see that 5 is in the correct place and deal with the next set of numbers [7,8,6] and continue on. We want to shrink the scope of what we are comparing as we loop through. You should get used to writing out each step of the process whenever you are tackling algorithms. By writing our this pseudocode, it breaks down the problem into steps that you can focus on one-by-one.
Implementing Selection Sort
Here’s where the fun part starts! Now we get to implement our thought process into actual code. So we want to write a function that accepts an array of integers. To start, we simply want to loop over every item so we create a simple for loop. Now, we mentioned we want to store the first element as the smallest value so far. So, we will create a variable called min and set it equal to i. This is the position of the smallest element, at least for right now when we first begin our loop. If at any point we find that there is an element with a lower value, we will change our variable lowest. Next, we want to compare that first item in our array to the second item in the array. Because we want to do this, we will create another loop using variable j to reference the next number after i. This is why j will equal i+1. I will post the function below so that you are able to follow along with the code as you are reading.
Love your console log
you want to initially see what our i and j values are. You can throw a console.log(i, j) in on line 5 before writing anything else. When you do so, you will see in the console, that we are comparing 0 to 1, 0 to 2, 0 to 3, 0 to 4 then the next time through 1 to 2, 1 to 3, 1 to 4 and so on. This is the comparison we are aiming to see. After one loop, we do not compare 0 again because it is set in that specific index and it is sorted so we know to move on. Don’t be afraid to use that console.log! It is such a powerful tool that always allows you a double check what you are doing is giving you what you are trying to achieve. I tend to throw console logs each step of the way to know where I mess up because image writing all this code and it not working. Now you have to go line by line backwards because you have no idea where something went wrong. So definitely use this tool as a best practice. It will only be in your favor at the end.
Now, we need a conditional inside of our loop to check what the value of the array is at the lowest and then compare it to the value of the array at j. This is implemented by line 5. If our array of j is less than the array of lowest, we will set our lowest to j. We update the value of lowest. At the end of our nested for loop on line 4 to 8, we now know the position of the lowest index. Here is where we want to perform our swap. Instead of simply performing our swap, we want to create a conditional that makes sure to only swap if our i does not equal the minimum anymore. This limits the amount of swapping that occurs in the background, which in-turn is always optimal for our code base. It’s important to optimize your code because it provides a logical understanding that you know what is going on and are proactively making it the best it can be.
Big O complexity of selection short
Selection sort is not the most efficient. For time complexity, it is O(n²). This is because we are roughly comparing every element to every other element in the array. As the length of the array grows, the number of comparisons grow at the rate of n*n, which is n². If we have a thousand items in our array, our time complexity is now going to be very large. It’s so much worse than simply comparing one item. However, if you have a case where you want to minimize the amount of swaps you are making, selection sort is preferably used. This is because we only make one swap at the end of each loop. Compared to maybe bubble sort which swaps over and over again until the largest number goes to the end.
Summary
Selection sort is a simple sorting algorithm that is great to know and understand. Again, it is great to also go over bubble sort if you haven’t done so yet. You can check out my blog post I wrote about it since it’s relatable to know after learning selection sort. These both will definitely help us have a strong intro into learning other sorting algorithms as well. There’s never too many algorithms to know so keep on learning!
