In this article, we will be discussing Insertion sort in C, C++, Java with examples, complete algorithm, and time complexity calculation.
Prerequisites: Bubble Sort, Selection Sort
Insertion sort is slightly different from the other sorting algorithms. It is based on the idea that each element in the array is consumed in each iteration to find its right position in the sorted array such that the entire array is sorted at the end of all the iterations.
In other words,it compares the current element with the elements on the left-hand side (sorted array).If the current element is greater than all the elements on its left hand side, then it leaves the element in its place and moves on to the next element. Else it finds its correct position and moves it to that position by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead.
Conclusion: Each iteration of insertion sort causes the sorted subset to grow, and the unsorted subset to shrink.
Let us consider an array with 5 elements, A = [7, 1, 23, 4, 19]. Below is how insertion sort works for this array.
Here is the pseudocode implementation of Insertion sort.
for i = 1 to n key = arr[i] j = i - 1 // comparing whether the first element is greater than the second element // if yes, then store the largest element to the next position while j >= 0 and arr[j] > key arr[j + 1] = arr[j] j = j - 1 end while // storing the smallest element in the correct position arr[j + 1] = key end for
We will now look into implementing insertion sort in C, C++, Java languages. In case you guys have solutions in other languages, then make sure you post it in the comments section of this article to help your friends.
Similar to Bubble sort and Selection sort, the time complexity of Insertion sort is also O(n). This is because, in the worst case, i.e when the given array is in the exact reverse order as that of the output, each element has to be compared with all the n elements in the sorted array. So this makes it n*n.