Insertion Sort is among the simplest sorting algorithms among various other sorting techniques. It is highly reflexive, stable, and of comparison-type. In this tutorial, we will go through a comprehensive understanding of insertion sort and concepts like – What is Insertion Sort, the Insertion sort algorithm usage, how the algorithm works with an example, and lastly, implement it in JavaScript.
What is insertion sort?
Insertion sort is a simple ordering of elements technique that sorts the elements of a given data structure in ascending or descending order whose approach is identical to the sorting of playing cards. This sorting technique has various applications such as database sorting, sorting customer entries, sorting data in data visualization, or arranging form data in web apps.
Algorithm of Insertion Sort
Think the first card is sorted in a game of cards, and then select an unsorted card. Put the chosen card on the left side if it is smaller than the first card, or else place the chosen card on the right side of the first card. Similarly, repeating the process with every card puts the cards in their rightful place.
Here is the algorithm of the Insertion Sort:
Algorithm:
Step 1: Assume the first element is already in the right place.
Step 2: Select the next element and keep it individually in a key.
Step 3: Compare the value in the key with all the elements in the sorted array.
Step 4: If the element of the sorted array is smaller than the current item, move to the next. Else, shift the bigger elements towards the right.
Step 5: Insert a new value
Step 6: Repeat till the whole array gets sorted.
How the insertion sort works
Let us take an example of an unsorted array:
12, 31, 25, 8, 32, 17
Initially, compare the first two elements, 12 and 31. Since they are already in ascending order, we'll not make any changes.
12, 31, 25, 8, 32, 17
12, 31, 25, 8, 32, 17
Compare the successive two elements, 31 and 25. Since 31 is greater than 25, we'll swap 25 with 31. And along with the swap, the insertion sort algorithm checks the swapped element with all elements in the sorted array.
12, 31, 25, 8, 32, 17
12, 25, 31, 8, 32, 17
Compare the next pair of elements, 31 and 8. Since 31 is greater than 8, we'll swap 31 with 8.
12, 25, 31, 8, 32, 17
12, 25, 8, 31, 32, 17
And with the swap, we find that the number 8 is smaller than 25. So we swap 8 with 25,
12, 25, 8, 31, 32, 17
12, 8, 25, 31, 32, 17
Now we find that the number 8 is smaller than 12. So swap 8 with 12,
12, 8, 25, 31, 32, 17
8, 12, 25, 31, 32, 17
Now compare the elements 31 and 32. We won't swap them because they are already in ascending order.
8, 12, 25, 31, 32, 17
8, 12, 25, 31, 32, 17
The next pair of elements are 32 and 17. We will swap them because 17 is smaller than 32.
8, 12, 25, 31, 32, 17
8, 12, 25, 31, 17, 32
After the swap, we found that 17 is smaller than 31. So swap 17 with 31,
8, 12, 25, 31, 17, 32
8, 12, 25, 17, 31, 32
After the swap, we found that 17 is smaller than 25. So swap 17 with 25,
8, 12, 25, 17, 31, 32
8, 12, 17, 25, 31, 32
Now the array is completely sorted.
Time and space complexities of Heap Sort
Heap Sort’s best-case complexity is O(n) which happens when the array is already sorted.
Its average-case complexity is O(n^2) which happens when the array elements are jumbled.
Its worst-case complexity is O(n^2) which happens when the array elements must get sorted in reverse order.
It has a space complexity of O(1).
Implementation of Insertion Sort in JavaScript
Code:
<html>
<body>
<script>
function insertionSort(arr, n)
{
let i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
//function to print the array
function printArray(arr, n)
{
let i;
for (i = 0; i < n; i++)
document.write(arr[i] + " ");
document.write("<br>");
}
let arr = [12, 31, 25, 8, 32, 17];
let n = arr.length;
printArray(arr, n)
insertionSort(arr, n);
printArray(arr, n);
</script>
</body>
</html>
Output:
To sum up:
In this article, we learned about insertion sort, its algorithm in simple steps, explaining how it works with an example, and a simple code to execute insertion sort in JavaScript.
It's one of the simplest sorting techniques that use repetitive swapping technique to sort its elements. Also, we gathered insight on how it uses different steps to perform its sorting tasks. We have also encountered the fact and applications where developers can use insertion sort.