Insertion Sort in Javascript
In last post we have posted about Bubble Sort algorithm in javascript. In this post we will write javascript program on Insertion sort.
In Insertion Sort to sort an array in ascending order
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
let arr = [64, 34, 25, 12, 22, 11, 90];
for (i = 1; i <= arr.length - 1; i++) {
let key = arr[i];
let j = i - 1;
// Move elements of arr[0..i-1],
// that are greater than key, to
// one position ahead of their
// current position
while (arr[j] > key && j >= 0) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
console.log(arr);
Time Complexity: O(n*2)
Reference :
https://www.geeksforgeeks.org/insertion-sort
Other Sorting Algorithms: