Insertion Sort in JavaScript

This blog post is written upon a task required in code fellows data-structures-and-algorithms javascript daily challenges.

In this blog post, I will focus on Insertion Sort. I will explain what is insertion sort and try to break down the concept of insertion sort step by step and providing the code, visualization and test for it.

Before going further, I will introduce myself. I am Ibrahim Banat a full stack web developer, specialized in MERN stack. I just finished a Bootcamp in web development from code fellows and sponsored by ASAC.

What is actually is the insertion sort?

Insertion sort is the simple sorting algorithm that is commonly used in daily lives while ordering a deck of cards. In this algorithm, we insert each element onto its proper place in the sorted array. This is less efficient than the other sort algorithms like quicksort, merge sort, etc. source.

Problem domain

writing a function called insertonSort which takes an array of integers as input and returns an array of these integers in sorted order from least to the largest.

Algorithm

The insertonSort the method works by building up a sorted array with the first element, then looking to the next element, if it's less than the previous elements, it swaps the element backwards until it's in a sorted position. it continues iterating through the input list, swapping new items backwards into sorted position until it reaches the end.

in conclusion:

  1. If the item is the first element, it’s already sorted.
  2. Inspect the next element
  3. Compare the element to the sorted sub-list.
  4. Swap the element in the sub-sorted array and push the element to its sorted position.
  5. Repeat until the list is ordered.

Pseudocode

InsertionSort(int[] arr)FOR i = 1 to arr.lengthint j ← i — 1
int temp ← arr[i]
WHILE j >= 0 AND temp < arr[j]
arr[j + 1] ← arr[j]
j ← j — 1
arr[j + 1] ← temp

Visualization

why we need a visualization for data structures?

Consequently exercises in computer science should also be supported not only by giving feedback to the program code, but also by visualizing objects and data structures produced by the program code created by learners. These visualizations of each individual solution would be an important link between the contents of the course and feedback for exercises. Moreover, they can help learners in debugging their program code, because an image of the data structure may give them some useful information without any need for inserting debug statements into their program code.

VISUALIZING DATA STRUCTURES IN AN E-LEARNING SYSTEM, M.Striewe & M.Goedicke source

for the visualizations, I am using a cool website called visualgo.

  • first thing first, this is our input list of integers:
input list of un-sorted integers

we will pass this list to the method, and the method will return a sorted copy of this list, we will come later to the implementation of the code.

  • Now we will take the first element, and since it’s the first element, it’s already sorted
  • moving to the next element, which is 44, figure where to insert this extracted element; comparing with sorted sub-list which contains 3.

and since 44 is not smaller than 3 then we will insert the element at the current position. the sub-sorted list should look like this:

  • Now we will extract the first un-sorted element which is 38. by comparing 38 to the last element in the sub-sorted list and since 38 is less than 44 then we will do a swap.
  • the algorithm will continue looping until it sorts all of the element in the array. The final sorted array should look like this:

Now after showing a visualization for the insertion sort, we will move to an important thing, which makes other sorting algorithms better than insertion sort, it’s the Big(O) notation.

Big(O) notation

Big O is defined as the asymptotic upper limit of a function. In plain English, it means that is a function that covers the maximum values a function could take. As we saw a little earlier this notation help us to predict performance and compare algorithms.

what makes insertion sort terrible is that it takes a quadratic growth rate because it contains nested loops.

The running times for insertion sort:

  • Worst case: O(n²).
  • Best case: O(n).
  • The average case for a random array: O(n²).
  • “Almost sorted” case: O(n).

now we will move to the implementation insertion sort in javascript.

Implementation

  1. first of all, we will create our function insertSort.

2. we will through the array starting to form the index of 1 because as we said the first element is already sorted.

3. now we will loop over the sub-sorted array from the last element until we reach the first element to make sure that we positioned our element correctly.

4. now we will compare if the current item in the input array is less than the previous item, then we will store the current item in a temp variable and swap it with the previous item

5. we will keep a loop over the sub-sorted array until the current item reaches it’s sorted position. and we will break the loop for the sub-sorted array.

6. final step we will return the array, which will be modified to be sorted.

in conclusion: the implementation of the algorthim looks like this:

we exported the function to use it inside the tests files.

Testing and Validation

I used the JEST library which is created by Facebook, first of all, I have imported the method which I exported earlier, and then I tested if the function returns a sorted array or not. I have tested also the length of the output array which should not be changed.

after that, we need to think about an edge case if the input array is empty. in this case, we need to add a condition that returns an exception if the input array was empty.

our function should look like this:

now if we want to test our method, we should pass an empty array to our method and expecting ‘Exception’ from it.

and it successfully worked as expected. this is the test coverage:

that's all for the insertion sort, I hope you enjoyed reading this article. this is a link for the code from My Github and see you in the next blog.

Full-Stack web developer || Electrical Engineer