HomeAbout MeContact

javascript algorithms - Insertion sort Explained using Javascript .

By Gopal Baskota
Published in JavaScript
January 11, 2021
1 min read

Insertion sort is another commonly used sorting algorithm. Like bubble sort, it is also simple and easy to implement. In insertion sort, the comparison starts by comparing the second element of the array with the first element. They are swapped accordingly. Then, the rest of the array is iterated. If the next element is larger than the current element, they are swapped. Then, the swapped element is compared with the already sorted portion of the array and if required, the element is inserted at the correct position.

Let’s understand with the help of an example.

  • [8, 2, 1, 3, 9] -> The sorting starts by comparing the second element, i.e. 2 with the first element, i.e. 8.
  • [2, 8, 1, 3, 9] -> Since 8 > 2, they are swapped. Next, 8 is compared with the next element, i.e. 1.
  • [2, 1, 8, 3, 9] -> 8 > 1, they are swapped. Next, 1 is compared with the sorted portion (left side of the element).
  • [1, 2, 8, 3, 9]-> Since 2 > 1, they are swapped. Next, 8 is compared with 3.
  • [1, 2, 3, 8, 9] -> 8 > 3, they are swaped. Now, 3 is compared with the sorted portion.
  • [1, 2, 3, 8, 9]-> As they are already in the order, no swapping is performed.
  • [1, 2, 3, 8, 9] -> Next, 8 is compared with 9. As 8 < 9, no swapping is performed.

The following is the implementation of insertion sort using JavaScript.

let arr =  [8, 2, 1, 3, 9]
let l = arr.length;
for (let i = 1; i < l; i++) {
    
    // first element of the unsorted array, starting from the second element        
    let current = arr[i];
        
    // last element of the sorted portion, starting from the first element
        let j = i-1; 
        while ((j > -1) && (current < arr[j])) {
                arr[j+1] = arr[j];
                j--;
        }
        arr[j+1] = current;
}
console.log(arr) // [1, 2, 3, 8, 9]

The time complexity of insertion sort is O(n^2) while the space complexity is O(1).


Tags

algorithmsjavascriptsortinsertionsort
Previous Article
javascript algorithms - Bubble sort Explained using Javascript .

Gopal Baskota

Full stack Web Developer

Topics

JavaScript
NodeJs
React Js

Related Posts

javascript algorithms - Bubble sort Explained using Javascript .
January 10, 2021
1 min
© 2021, All Rights Reserved.

Quick Links

Advertise with usAbout UsContact Us

Social Media