Insertion sort in JavaScript

Insertion sort in JavaScript

Insertion sort is a simple and stable sorting algorithm that picks an element from an unsorted list and inserts it into the sorted list at the appropriate position. While the term stable algorithm refers to the scenario where two equivalent elements appear identically, then a stable algorithm holds the elements at their relative positions after the execution of the sorting algorithm is completed.

Insertion sort algorithm is very helpful in those cases where we have a smaller number of elements in a list or where most of the list is already sorted and fewer elements are misplaced.

How Insertion Sort Works

Let’s consider an example to better understand the logic behind the insertion sort. Suppose we have an unsorted array of 6 elements and we have to sort them using insertion sort:

Now to sort the above array, we will iterate the array from index 1 to the last index. Initially, we assume the 0th index of the array is sorted, thereafter we will make a comparison of the current element with its prior element. If the current element is less than the prior element then we will swap their positions.

First Step
In the first step, we will compare index 1 with index 0, the value of the first index ‘47’ is greater than 0th index value, so there will be no change in the first step (elements wouldn’t swap):

Second Step
Now, in the second step, we will assume that the first two elements are sorted, so cursor will be at index 2, and we will compare index 2 with its prior elements:

Since ‘25’ is smaller than ‘47’, swap ‘25’ and ‘47’. Next, ‘25’ is also compared with the 0th index value. ‘25’ is greater than ‘15’ so it wouldn’t be swapped.

The array after the second step will be updated as:

Third Step
Here in the third step, we consider the first three values are sorted and the cursor will be at the third index. So, we will compare the third index with its prior values:

At index 3, ‘55’ is compared with each element one by one but it is greater than all of its prior elements so there will be no change in the position of array elements.

Fourth Step
Now we are at index 4, where we have a value ‘20’ and we have to compare it with all the prior elements of the array:

Since ‘20’ is less than ‘25’, ‘47’ and ‘55’ so it will be inserted at the first index, and ‘25’, ‘47’ and ‘55’ will be moved to the right side by one index (i+1 index) from their current indexes.

The updated array will be:

Fifth Step
Now we are at index 5 where the current value is ‘10’ which is the smallest among all the array values, so it will be inserted at the 0th index.

In this way, the whole array will be sorted using insertion sort:

As we are done with the conceptual part of insertion sort, now we will implement this concept in JavaScript.

Implementation of Insertion Sort in JavaScript

The code for implementing the insertion sort in javascript is as follow:

function insertion_Sort(input_array, array_length)
{
    let i, pivot_value, j;  
    for (i = 1; i = 0 && input_array[j] > pivot_value)
        {
            input_array[j + 1] = input_array[j];
            j = j – 1;
        }
        input_array[j + 1] = pivot_value;
    }
    return input_array;
}  
let input_array = [15,47,25,55,20,10 ];
let array_length = input_array.length;
insertion_Sort(input_array, array_length);
console.log(“final sorted array : “, input_array);

In the above code, we created a function “insertion_sort” and passed it the input array and array length. Then we iterated the loop until the length of the array.

Inside the loop, we selected the ‘pivot_value = input_array[i]’ as a pivot value to make a comparison of the current element with its prior elements and set “j= i-1” which represents the last element of our sorted array.

Here in each iteration, the current element is assigned to the pivot value and the pivot value will be considered as the first element of the unsorted array in each step.

We utilize a while loop to sort array elements, here in this loop we compare the current element with its prior elements. If the current element is less than any of the prior elements, and we found the appropriate position to insert that element in the sorted array then we insert that element at the appropriate position and move the other elements one place to the right side. And the whole phenomenon is repeated for each step until the array is sorted completely.

Output

Finally, we call the “insertion_sort” function and print the sorted array at the console of the browser using the “console.log” method. The output of the insertion sort algorithm will be:

Conclusion

Insertion sort is a sorting algorithm that sorts one element at a time. It inserts the element at the appropriate position one by one to create one sorted array. It provides efficient results if the number of array elements is small and most of the array elements are already sorted.

In this article, we considered an example to figure out the logic of insertion sort, we discussed the working of the insertion sort algorithm with respect to each step and present the updated array after each step. And finally, once we perceived the idea behind the insertion sort then we implemented it in JavaScript.

Leave a Reply

Your email address will not be published. Required fields are marked *