Insertion Sort works as follows:
The first step involves the comparison of the element in question with its adjacent element.
And if at every comparison reveals that the element in question can be inserted at a particular position, then space is created for it by shifting the other elements one position to the right and inserting the element at the suitable position.
The above procedure is repeated until all the element in the array is at their apt position.
Let us now understand working with the following example:
Consider the following array: 25, 17, 31, 13, 2
First Iteration: Compare 25 with 17. The comparison shows 17< 25. Hence swap 17 and 25.
The array now looks like:
17, 25, 31, 13, 2
Second Iteration: Begin with the second element (25), but it was already swapped on for the correct position, so we move ahead to the next element.
Now hold on to the third element (31) and compare with the ones preceding it.
Since 31> 25, no swapping takes place.
Also, 31> 17, no swapping takes place and 31 remains at its position.
The array after the Second iteration looks like:
17, 25, 31, 13, 2
Third Iteration: Start the following Iteration with the fourth element (13), and compare it with its preceding elements.
Since 13< 31, we swap the two.
Array now becomes: 17, 25, 13, 31, 2.
But there still exist elements that we haven’t yet compared with 13. Now the comparison takes place between 25 and 13. Since, 13 < 25, we swap the two.
The array becomes 17, 13, 25, 31, 2.
The last comparison for the iteration is now between 17 and 13. Since 13 < 17, we swap the two.
The array now becomes 13, 17, 25, 31, 2.
Fourth Iteration: The last iteration calls for the comparison of the last element (2), with all the preceding elements and make the appropriate swapping between elements.
Since, 2< 31. Swap 2 and 31.
Array now becomes: 13, 17, 25, 2, 31.
Compare 2 with 25, 17, 13.
Since, 2< 25. Swap 25 and 2.
13, 17, 2, 25, 31.
Compare 2 with 17 and 13.
Since, 2<17. Swap 2 and 17.
Array now becomes:
13, 2, 17, 25, 31.
The last comparison for the Iteration is to compare 2 with 13.
Since 2< 13. Swap 2 and 13.
The array now becomes:
2, 13, 17, 25, 31.
This is the final array after all the corresponding iterations and swapping of elements.
INSERTION-SORT(A) for i = 1 to n key ← A [i] j ← i – 1 while j > = 0 and A[j] > key A[j+1] ← A[j] j ← j – 1 End while A[j+1] ← key End for
Following are C, C++, Java and Python implementations of Insertion Sort.
Click Here for code:
Characteristics of Insertion Sort
It is efficient for smaller data sets, but very inefficient for larger lists.
Insertion Sort is adaptive, that means it reduces its total number of steps if a partially sorted array is provided as input, making it efficient.
It is better than Selection Sort and Bubble Sort algorithms.
Its space complexity is less. Like bubble Sort, insertion sort also requires a single additional memory space.
It is a stable sorting technique, as it does not change the relative order of elements which are equal.
Complexity Analysis of Insertion Sort
Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will still execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)
The Tech Platform