Programming with JS: Insertion Sort
Understanding data structures, algorithms and basic programming concepts is essential for one to become a better developer. Nowadays most of those problems are solved using modern tools and libraries, but having deeper knowledge in that area will definitely broaden your perspective of software development.
Personally, for me it was pretty hard to get a grasp on some of those concepts, because I was not using them in my day-to-day work. I’m writing this series to improve my own understandings on those topics and help other people like me.
What is Insertion Sort?
Insertion sort is another popular sorting algorithm, even though it’s not as performant as quick sort or merge sort, for example. The way it works is that it splits the array into two sections — a sorted and an unsorted one. We don’t know if any of the items are in place yet, so we will start our sorted list with the first item (an array of a single item is sorted).
Then we start going through the other items in the array. For each one we must find it’s proper place in the sorted array. We do that by finding the first smaller item or until we reach the beginning of the sorted list. It will probably better if i show you an example of what’s actually going on. The sorted array will be bold.
5, 9, 13, 4, 1, 6 // the only sorted part is the first item5, 9, 13, 4, 1, 6 // 9 > 5 so we don't move it5, 9, 13, 4, 1, 6 // 13 > 9 we don't move it4, 5, 9, 13, 1, 6 // compare all to 4, until we reach the head 1, 4, 5, 9, 13, 6 // compare all to 1, until we reach the head1, 4, 5, 6, 9, 13 // first smaller item is 5, place 6 before it
How does it work?
The special thing about insertion sort is that we don’t swap items. Even though it seems like we’re swapping them and moving them around, what actually happens is that we loop through the sorted part and find the first smaller item (or the head of the array) and place our item there. What do we do with the items before that? Since we’re looping through each one of them, every higher number is actually moved one index ahead (well, not moved — copied) in order to make way for the current item.
It’s better to give a code representation of the actual algorithm so you can get a better understanding of what is happening:
Once you understand the concept, transferring it to code is not hard at all. I’d argue that this is one of the easier algorithms to implement. Spend some time on it, write it down on a sheet of paper, get a hold of the idea and coding it won’t be a problem.
Thank you for the read, if you’re looking for more computer science JS stuff, I’m currently writing a whole series on them. If you want general JS content, you can take a look at my profile.
Programming with JS:
Recursion: https://hackernoon.com/programming-with-js-recursion-31371e2bf808
Merge Sort: https://medium.com/@KondovAlexander/programming-with-js-merge-sort-deb677b777c0
Binary Search: https://medium.com/@KondovAlexander/programming-with-js-binary-search-aaf86cef9cb3
Insertion Sort: https://medium.com/@KondovAlexander/programming-with-js-insertion-sort-1316df8354f5
