Sorting Algorithms: Insertion Sort

In this next series of Sorting Algorithms, I will be talking about Insertion Sort!

What Is Insertion Sort?

Insertion Sort is a sorting algorithm that consumes an input element for each repetition and grows a sorted output. How this works is, at each iteration, the algorithm removes/ holds one element from the array, looks for the location it belongs to within the sorted list, and inserts that element back into the array at the correct sorted index.

Pseudocode

• Start by picking the second element in the array.
• Compare the second element with the element before i. Swap if that second element is greater than the one before i.
• Continue to the next element, and if it is in the incorrect order, loop through the sorted portion, (the left side) to place that element in the current place.
• Repeat till array is sorted.

The Code With Comments

function insertionSort(arr){
  //start looping at first index
  for(var i = 1; i < arr.length; i++){
    //assign a plae holder varible at the index of i to keep track f the value we are looking at
    var currentVal = arr[i]
    //start working backwards with variable j at the value behind i 
    // ex: if i = 9, we want to start comparing the value of i to the value of j --> j = 77
    //we need to keep going while j is greater than 0 (his up to the beginning of the array)
    //and while j is greater than currentVal variable 
    for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
          //ex: is currentVal = 9 smaller than arr[j] = 77 value, yes! then move arr[j] up in the array 
          //[2,4,5,20,77,77]            9 is waitning for its placement
      arr[j + 1] = arr[j]

    }
    //after the loop is done, we have found our placement for currentVal
    //we assign arr[j + 1] to currentVal b/c there will be a duplicate of arr[j] where it was before 
    //       j
    // [2,4,5,20,20,77]          9 waiting
    //       j+1 --> this is where 9 should be now
    arr[j + 1] = currentVal 
  }
  return arr
}
insertionSort([2,4,5,20,77,9])

The Code Without comments

function insertionSort(arr){
  for(var i = 1; i < arr.length; i++){
    var currentVal = arr[i]
    for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal

  }
  return arr
}

insertionSort([2,4,5,77,1,9])

The Explanation

Now, if sorting algorithms have got your mind all boggled up, don't worry, I was the same way when I first started learning.

Basically, we want to iterate over the array with our variable i at the first index. By first I mean the index of array[1]. We then assign that element into a variable called currentVal.

Now we need to start thinking about how we will be moving backward in our array. We do this by iterating through our array again with a variable j at the index behind i. During this loop, if the current value is smaller than arr[j], we need to move it hold on to that value you, go down the list of elements, and find the index it belongs to.

  for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
      .....
    }

Our j variable does this by shifting the larger value elements up in the array.

 arr[j + 1] = arr[j]

Once we find that our currentVal variable is actually larger than an element at arr[j] we move up by one in the array and assign currentVal to that index

    arr[j + 1] = currentVal

Finally, out of the loop, we can return the sorted array.

Time & Space Complexity

The best-case scenario for a sorting algorithm like insertion sort is O(n).
We can obtain this during each iteration, the first remaining elements of the input is only compared with the right-most element of the sorted subsection f the array. This is achieved by using a while loop instead of a nested for loop.

Now, the worst-case senario for insertion sort is O(n^2), which is a quadratic running time. That is because, there is a nested for loop, which is looking through our array backward. Looking through and shifting the sorted subsection of the array before inserting the element into its right position.

The Conclusion

Now, even though Insertion sort is much more efficient & faster than Bubble sort and Selection sort when it comes to small array lengths. It can not handle a large list of arrays. However, there are more advanced sorting algorithms that I will diving into next time on this series of Sorting Algorithms! So Stay tuned for the next blog post :)

Happy Coding!

References

Learn more about Insertion sort