Searching and Sorting Algorithms in Javascript — Part 4(Insertion Sort).
Insertion sort algorithm is another sorting algorithm that sits in the same rank with Bubble and Selection sort. I’ll tell you all about the differences and similarities later, then you can pick which one you prefer. For now, let’s focus on how it works…
How does this guy work?
One beautiful thing about this algorithm is how it does it’s sorting. It’s pretty neat in my opinion (p.s: Don’t say this to anyone outside, you might get stoned for it!!!).
It follows the main Idea that any number in an array with more than one element has numbers to the left of it except the first element of that array. Here’s what that means:
Say we have an array of 5 numbers — [1, 2, 3, 5, 6, 7]. Any number in the array except 1 has some number to the left of it. What we can make sure is that, starting from the second element in the array, we make sure that every number to the left of it is in the position it’s supposed to be in terms of rank. So:
- We loop through every number in our array (starting from the second number)
- Start another Loop through all the elements to the left of that number and try to place that number where it belongs.
Let’s see how this works in code:
I hope the code above is clear enough. If somethings aren’t clear yet, do checkout the visual representation of the algorithm on visualgo — https://visualgo.net/en/sorting.
That’s it for insertion sort guys………. Is it 👀?
What’s the difference between the 3 (selection, bubble and insertion)?
In terms of implementation, it’s up to you to pick which one makes more sense to you. But using Big O to judge, they all have a worst-case time complexity of O(n²), average time complexity of O(n²). For best case, bubble sort and insertion sort have a time-complexity of O(n) while selection sort has O(n²).
Have it in mind that, in Big O terms, we don’t really care much about the average and best case time complexity. We’re always judging by the worst case so, it’s up to you now to decide which one you’re adding to your toolbox.
That’s it for insertion sort guys…. See you on the next one!
