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

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.

#include<stdio.h>
int main()
{
int i, n, j, temp, min, key;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for (i = 1; i < n; i++)
{
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 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
// storing the smallest element in the correct position
arr[j + 1] = key;
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
#include<iostream>
using namespace std;
int main()
{
int i, n, j, temp, min, key;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for (i = 1; i < n; i++)
{
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 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
// storing the smallest element in the correct position
arr[j + 1] = key;
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
import java.util.Scanner;
public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i, j, temp, min, key;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
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;
}
for(i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}

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)

Also See Similar DS Sorting Techniques