Sorting Algorithms: Selection Sort
This week I’ve chosen to continue discussing the topic of Sorting Algorithms, specifically the Selection Sort Algorithm. If you would like a more in depth breakdown into the fundamentals of sorting algorithms, check out my previous blog, Sorting Algorithms: Bubble Sort — where I go further into some of the more fundamental concepts of Sorting Algorithms like swap.
What is Selection Sort?
Selection Sort is similar to bubble sort, but instead of the larger elements moving to the end of the array, the smaller values are selected and positioned to the front of the array one at a time. In this sorting algorithm, we loop from the beginning to the end of the array looking for the lowest value in each iteration. Instead of swapping throughout the loop, we take the first value and compare it with all values in the array. If the first value isn’t the lowest, we swap it with the lowest value in the current iteration of the array. We repeat this process until we have a sorted array.
Why is it called Selection Sort?
In short, each time we loop through an array using Selection Sort, we are selecting the lowest value in the array and swapping it with the first element. The two elements we are swapping or considering to swap, are/is (a) the first element in the current iteration of our loop, and (b) the lowest value in the current iteration of our loop. If the first element is also the lowest element it stays at it’s current location in the array and we move on to the next run of the algorithm.
Selection Sort Pseudocode
- First we define a function called selectionSort that takes in an array as an argument.
- Next, we will loop through the array and create a variable within the loop to store the smallest value setting it equal to the first value to start
- Compare this variable to the next item in the array until or if you find a smaller value.
- And if the current variable is no longer the smaller value, save the new smaller value to be the variable.
- Continue until the end of the array. If the new smaller variable is not in the index of the initial value at the start of the loop, swap the two values.
- Repeat this process, moving onto the next element until the array is sorted.
function selectionSort(array){
const swap = (array, index1, index2) =>
([array[index1], array[index2]] = [array[index2], array[index1]])
for (let i = 0; i < array.length; i++){
var lowest = i
for (let j = i+1; j < array.length; j++){
if (array[lowest] > array[j]{
lowest = j
}
}
if ( i !== lowest) swap(array, i, lowest);
} return array;
}selectionSort([34, 22, 10, 19, 17]);
What is going on in the snippet above?
So in our function above, we are creating a swap helper method. Below that we begin a loop iterating through the array. We declare a variable called “lowest” which is equal to i which on the first loop is equal to 0. This value will represent the lowest value in our array. The i will increment to the length of the array by the final iteration. The value in “lowest” is our starting point. In a nested loop we are setting j equal to i plus one, so that we are then able to compare the first index (aka, lowest) , to the next index. While j is less than the length of the array we will continue to iterate through the array checking for our condition: to find the lowest value in the iteration. If while we are iterating, we find a lower value, we will set the “lowest” variable equal to this new index. Finally after having gone through both loops, we have a final condition before we implement the swap. If i does not equal lowest, we swap the values of i and the lowest.
A disadvantage to this sort method, is that if we had a nearly sorted array, it will continue run checking through all of the conditions and all of the elements in the array. It’s useful to know still and one of its strengths lies in its readability.
