Hello 🙂 I hope you’re keeping well ?
In today’s post I am going to talk a bit about our third sort which is Insertion Sort. actually one of the easiest sorting we have out there. with insertion sort the point to note here is that the in-place first element of the collection is already sorted so there wouldn’t be any need to start sorting from the first element instead the focus should rather be on the next element which will be used to compare the previews one and this time around we won’t swap, well we could swap but that could be a bit confusing to grab so instead we hold the current value and shift it to the right if the presiding element is less than that of the current value. I like to think of this type of Insertion sorting as a card game and imagine you’re given a cards one at a time and you received the first one waiting for the second card that you place right a the place it belongs arranging it in your own order, the next card that comes to you will definitely be placed either after or before the previous one, doing so will insert each card at their right place. let’s take a look at the various solutions now.
function insertionSort(arr) {
let currentVal;
let j;
for (let i = 1; i < arr.length; i++) {
currentVal = arr[i];
for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = currentVal;
}
return arr;
}
console.log(insertionSort([2, 1, 9, 76, 4]));
This function takes in an array, first we declare two variables currentVal & j, in the first iteration we start the element from the second in the list as our current value, remember we said the insertion sort assumes the first value is already sorted so then we go into our second loop to determine the next element for the comparism which is to be assigned to j, as j decreases we keep it’s value in check if for some reason it is greater then the current value in memory then we assign the next element position to j as our current value. keep doing the same thing until j decreases to position 0 or greater.
We could equally implement the same scenario with a while loop. Let’s take a look
function insertionSortAlt(arr) {
let current;
for (let i = 1; i < arr.length; i++) {
current = arr[i]; let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]; //current is j now
j--; //reverse order
}
arr[j + 1] = current; //set to current values
}
return arr;
}
let data = [5, 8, 6, 98, 23, 225, 4, 7, 93, 52];
console.log(insertionSortAlt(data));
The same implementation with a while loop which will give us equal result.
remember I said earlier we could use a swap ? well this implementation looks a bit controversial and many may ague it does not fully follow the rules for insertion sort but it’s worth mentioning it to judge it yourself .
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) { for (j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; //swap
} else {
break;
}
}
}
return arr;
}
I personally see this logic to be much simpler but not of a popular vote because of the reason above. here we swap the values anyway without calling for starting with position 0 which probably make it a bubble sort not setting a minimum so become a selection Sort yet we arrived at the same goal.
Time complexity of Selection sort in it best case scenario is O(n) Linea if already sorted but goes to O(n²) Quadratic as soon as it start the second loop in the solution and Always giving us a space complexity of O(1) Constant.
I hope you’ve learn something from this post, until the next keep safe.