Sorting Algorithms Part 3: Selection Sort
Today we’re going to learn about our third simple sorting algorithm: selection sort. Selection sort, like the two sorting algorithms we’ve looked at previously, takes an array or list as it’s input and outputs that same array with all entries sorted in ascending order.
Let’s walk though how selection sort works. Take the array, [3, 8, 5, 4, 7, 1, 6], as an example. To sort our array elements, we are going to go through each element and find the smallest element that comes after our selected element in the array. If the smallest entry is less than our selected element, we are going to swap our current entry with the smallest entry. Using our example array, we would select the first element, 3, and check for the smallest element after 3 in our array. It looks like the smallest element after 3 is 1, and since 3 is greater than 1, we swap those two elements. Our new array looks like this: [1, 8, 5, 4, 7, 3, 6]. Our next iteration we select the second element, 8. Looking at all the array elements after 8 we find that 3 is the smallest, so we swap 3 and 8, to get the array [1, 3, 5, 4, 7, 8, 6]. Here’s a diagram of the remaining swaps:
[1, 3, 5, 4, 7, 8, 6] 5 > 4, swap
[1, 3, 4, 5, 7, 8, 6] 5 < 6, no swap
[1, 3, 4, 5, 7, 8, 6] 7 > 6, swap
[1, 3, 4, 5, 6, 8, 7] 8 > 7, swap
[1, 3, 4, 5, 6, 7, 8] ordered array!
So how do we do all that in code? Well, we have a couple of options. The first is to use a helper function like so:
function selectionSort (array) {let ordered = []let run = array.lengthfor(let i=0; i<run; i++){let smallest = selectionHelper1(array)ordered.push(array[smallest])array.splice(smallest, 1)}return ordered}function selectionHelper (array) {let j = 0for(let i=0; i<array.length; i++){if(array[i] < array[j]) j = i}return j}
Looking at this code, we can see that we are creating a new array to house our sorted elements, and then iterating though our original array one element at a time. For each element of our original array, we use our helper function to find the smallest value which occurs after that element. We then push the smallest value to our new array and remove it from our original one. Once we’ve gone through all our elements, we simply return our new array with all the entries in ascending order. You might notice though, that this isn’t very space or time efficient since it requires us to create a whole new array and runs a nested loop (we’re running a loop inside the for loop every time we call the helper function). This makes our time complexity O(n2) and space O(n). We can make this a little bit more efficient by doing all of our sorting in place so our space complexity is only O(1) by using a nested loop like this:
function selectionSort(array) {for(let i=0; i<array.length-1; i++){let index = ifor(let j=i; j<array.length; j++){if(array[j] < array[index]){index = j}}if(i<index){[array[i], array[index]] = [array[index], array[i]]}}return array}
Here we’re running an outer for loop that goes through each element of our array in order and an inner for loop that finds the index of the smallest element after our selected one that is also smaller than our element. We then swap our selected element with the smallest element we found and simply return our sorted array at the end. Our time complexity is still a bit slow, especially for longer lists, but at least we don’t have to worry about it taking up memory. We’ll look at an even more efficient sorting algorithm, quick sort, next week that resolve some of these issues. Until then happy learning and have fun exploring selection sort!
Resources:
https://stackabuse.com/selection-sort-in-javascript/
https://dev.to/seanwelshbrown/implementing-a-selection-sort-algorithm-in-javascript-9of
