Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Insertion Sort in C, C++, Java with Examples & Time Complexity | FACE Prep

Published on 12 Mar 2020

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


What is Insertion Sort Algorithm?


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.


insertion sort in c


Conclusion: Each iteration of insertion sort causes the sorted subset to grow, and the unsorted subset to shrink.


Insertion Sort Example & Working


Let us consider an array with 5 elements, A = [7, 1, 23, 4, 19]. Below is how insertion sort works for this array.


examples of insertion sort program in c

Insertion Sort Pseudo Code


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


Insertion Sort in C, C++, Java


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.


C
C++
Java

Output
Input- 5 12 3 4 9 6 Output- 3 4 6 9 12


Insertion Sort Time Complexity


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.


  • Best case time-complexity:O(n). This occurs when the given array is already sorted.
  • Worst case time complexity:O(n)
  • Space Complexity:O(1)


Check out more Data Structure Questions


Also See Similar DS Sorting Techniques


If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in