We want to implement the algorithm until all of the errors are gone and the final return array is in sorted order.
The inside of the loop is actually pretty simple.
We grab the element at the current index, i, and then check the remainder of the array for any elements that are smaller than it.
Once you have found the smallest element, if it is not already at the current index, swap it with the smallest one.
let smallest = nums[i]let swapIndex = i// Search the remainder of the array for the smallest numberfor (let j = i + 1; j < nums.
length; j++) { if (nums[j] < smallest) { smallest = nums[j]; swapIndex = j }}// Swap if the smallest number isn't at the current indexif (i !== swapIndex) { const tmp = nums[i] nums[i] = smallest nums[swapIndex] = tmp}If you put this code inside of the skeleton code above with the loop invariant checks, you will see that all of our errors are gone and it just outputs the final result![1 2 5 7 8]Taking out the loop invariant checks, our final algorithm is:Run Time Analysis of Selection SortWe are going to wrap up this post with a runtime analysis of the selection sort algorithm.
As we learned in the previous section, the selection sort algorithm only needs to run up until the n-1 element.
With that in mind, the outer loop can be represented as a summation from i=1 to n-1.
For our inner loop, we only have to iterate over the part of the array that has not yet been sorted.
In other words, if we have sorted i elements, then we only need to perform n-i iterations of the inner loop.
That gives us our summation formula:Both the best-case and the worst-case runtime for selection sortCoincidentally, this is the exact same result that we got for a worst-case insertion sort and it is Ɵ(n²).
A huge difference between selection and insertion sort, however, is that selection sort has the same runtime for both its best and worst case.
There are no conditions that could possibly short-circuit the inner loop.
It always has to loop through the entire array to check that there are no smaller elements remaining.
This means that insertion sort is always going to be better, on average.
This makes selection sort impractical to ever use, but I still found this exercise to be educational nonetheless.
.