Sort an Array with a Nested for Loop using Insertion Sort in JavaScript
Insertion sort is another sorting algorithm that closely resembles how we might sort items in the physical world. We start at the second item in our collection and make the assumption that this item is a sorted list of length 1. We then compare all the items before it and determine if it needs to be "inserted" to the left or right of our item. We then move onto the second item, again comparing it to every item before it in the list, inserting those items correctly.
Because this algorithm requires two loops, one inside the other, the worst case scenario of our algorithm still requires a time complexity of O(n^2). This is also an inefficient sorting algorithm, but if our list is mostly sorted already, it will perform a slight bit better than bubble sort.
Instructor: [00:00] To create our insertion sort algorithm, we'll create a function accepts an array, sorts it, and then returns it. Insertion sort works by using a nested loop. We'll take the first item in the list and assume we have a sorted list of length one. We'll then compare the next item to it and place it before or after it depending on which item is greater.
[00:23] Since we'll have two loops going, we need to create two iteration variables. We'll use I and J. Next, our outer loop will start at the second element in the array, thus I will start at the value of one. This loop will loop through the entire length of the array from the second item. We can use I is less than array.length, and we can increment I.
[00:49] We'll have an inner loop that starts at the first item in our list, so J will start at zero. We only want to loop up to the current item being iterated over in our outer loop, so our second statement in this is J is less than I. Here, we want to increment J.
[01:07] Remember, this inner loop will reset each time our outer loop advances to the next number. What we want to do inside our two loops is compare the item at array index I to array index J. If item I is less than item J, then we want to move the item I to the position of item J.
[01:28] I'm going to use array destructuring to get an item variable. I'm going to use the splice method to get it. We want to splice at the index of I. We want to only get one item deleted and given back to us. I'm going to use the splice method again to insert that item at the J position.
[01:48] That's the insertion sort algorithm, but we want to be able to visualize it. I'm going to use the print array utility method I've brought into the file in order to print each time we make a comparison. I want to add one more print array before we return the array.
[02:04] This way, we'll get to see the array in its final sorted form. Now that I have that, I can create an array of unsorted numbers and pass those numbers to our insertion sort function. If I save that and print that to the terminal, we can examine how the algorithm worked through each iteration.
[02:24] If we scroll up, we could see how 10 moved one spot during the first one, a few more spots each time afterwards. What this reveals to us is how the inner loop of J was comparing more numbers each time I got a little bit bigger. Eventually, we could see 10's moved all the way to the right and that our list is sorted and organized.
Hi Fabian,
I highly doubt that splice uses loops under the hood. Arrays are very fast with operations involving indices, since they are essentially stored as hashes with each key as an index. Thus, splice is likely an O(1) operation under the hood, just making a direct copy of the items and doesn't loop through each item. For the sake of teaching the concept, this is a fine way of showing insertion sort.
Hi Kyle, thank you for the clarification :)
Hi kyle, I'm wandering if this algorithm could be more efficient by usign destructuring(probalbly I'm using the wrong term) than using "splice" method, I'm not sure but splice could cause another iteration in the array, isn't it?.
Therefore the code would be: