Insertion Sort in C: Insertion Sort is a very simple and adaptive sorting technique, widely used with small data items or data sets. It’s more efficient with the partially sorted array or list, and worst with the descending order array and list. Below is the Table of content that we are going to learn in this complete article.

Table of Content

• Advantages and Disadvantages of Insertion Sort
• Real Life Example
• Pseudocode of Insertion Sort
• Complexity
• C Program for Insertion Sort using For Loop
• Insertion Sort using While Loop
• C Program for Insertion Sort using Functions
• The output of Each Program
• Analysis of Output

How does Insertion Sort Work?

Insertion sort is a sorting technique, which use to sort the data in ascending or descending order, like other sorting techniques (Selection, Bubble, Merge, Heap, QuickSort, Radix, Counting, Bucket, ShellSort, and Comb Sort).

It’s very useful with a small data set or partially sorted data and not efficient if data is sorted in descending order and you want to sort data in ascending order.

The implementation is very easy, Jon Bentley implements it in just 3 steps and the optimised version in just 5 steps.

Advantages of Insertion Sort

There are many advantages, and below is a list of all advantages.

• implementation is very simple
• It’s very efficient for smaller data
• It is more efficient or better compare to Selection Sort and Bubble Sort
• it’s adaptive when a partially sorted array or list is provided as input.
• Its space complexity is very less O(1).
• It is a stable sorting technique
• It is a stable technique, as it does not change the relative order of equal elements.

Disadvantages of Insertion Sort

As we know that all sorting algorithms have some disadvantages so insertion sort also has, there are a few lists of demerits of insertions sort

• Not efficient for larger lists.
• It does not perform as other sorting algorithms perform.
• It is only useful for the few data list or if an array is mostly sorted.

Real-Life Example

While playing a card we use insertion sort when 4 players are playing and all of them have 13 Cards, after that, they arranged the card according to colour, type, or ascending or descending order, it depends on the player’s habits but one thing is clear they pick a card from the 13 and set the card in the correct position.

Pseudocode of Insertion Sort

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

The Complexity

Sr. No.	Complexity	Time	Space
1	Best-Case	О(n)	–
2	Average Case	О(n^2)	–
4	Worst-Case	О(n^2)	–
5	Space Complexity	–	О(n) Total, O(1) Auxiliary

All the solutions are tested on Dev-C++ and online compilers, If you still face any issues comment below we will help you on the spot.

Insertion Sort Using For Loop

/* C Program for Insertion Sort Using FOR Loop */ 

#include <stdio.h>

int main() {
  /* "Insertion Sort in C Program". This Programming Solution is belong to Simple Categories in C Language. -by https://tutorialsbookmarks.com */

  int number, i, j, temp, count = 0;

  printf("Enter How Many Numbers You Want to Sorted: ");
  scanf("%d", & number);
  /* Array Size is equal to the numbers you entered, by using this method we can save the size. */
  int a[number];

  printf("\n\nEnter the Numbers: ");
  /*
    Storing Numbers in an Array
	*/
  for (i = 0; i < number; i++) {
    scanf("%d", & a[i]);
  }
  /* Sorting Numbers by using Insertion Sort */
  for (i = 1; i <= number - 1; i++) {
    for (j = i; j > 0; j--) {
      if (a[j - 1] > a[j]) {
        temp = a[j];
        a[j] = a[j - 1];
        a[j - 1] = temp;
        /* For Counting Total Number of Iterations */
        count++;
      }
    }
  }
  printf("\n\nSorting Result in Ascending order of Insertion Sort: ");
  for (i = 0; i < number; i++) {
    printf(" %d  ", a[i]);
  }

  /* For printing, the array insertion sort results in Descending order remove this comment
	printf("\n\nSorting Result in Descending order of Insertion Sort: ");
	for(i = number-1; i >= 0; i--)
    {
        printf(" %d  ", a[i]);
    } 
    */

  printf("\n\n");
  printf("Total Number of Iterations Needed %d", count);
  printf("\n\n");
  return 0;
}

The Output

Insertion Sort Using While Loop

/* C Program for Insertion Sort While loop*/
#include <stdio.h>
int main()
{
  /* "Insertion Sort in C Program". This Programming Solution is belong to 
  Simple Categories in C Language. -by https://tutorialsbookmarks.com
  */	
	
    int number, i, j, temp, count=0;
    
    printf("Enter How Many Numbers You Want to Sorted: ");
    scanf("%d", &number);
    /* Array Size is equal to the numbers you entered, by using this method we can save the size. */
    int a[number];
    
    printf("\n\nEnter the Numbers: ");
    /* Storing Numbers in an Array */    
    for(i = 0; i < number; i++)
    {
        scanf("%d", &a[i]);
	}
    /* Sorting Numbers by using Insertion Sort */	
    i = 1;
    while( i <= number - 1)
    {
        j = i;
        while( j > 0 && a[j - 1] > a[j])
        {
            temp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = temp;
            j--;
            count++;
        }
        i++;
    }
    printf("\n\nSorting Result in Ascending order of Insertion Sort: ");
    for(i = 0; i < number; i++)
    {
        printf(" %d  ", a[i]);
    }
    /* For printing, the array insertion sort results in Descending order remove this comment
    
	printf("\n\nSorting Result in Descending order of Insertion Sort: ");
	for(i = number-1; i >= 0; i--)
    {
        printf(" %d  ", a[i]);
    } 
    */    
    
    printf("\n\n");
	printf("Total Number of Iterations Needed %d", count);
    printf("\n\n");
    return 0;
}

The Output

Insertion Sort Program Using Functions in C

/* C Program for Insertion Sort Using Functions*/
#include <stdio.h>
void insertion(int a[], int number) 
{
    int i, j, temp;
	int count=0;
    
    for(i = 1; i <= number - 1; i++)
    {
        for(j = i; j > 0 ; j--)
        {
        	if (a[j - 1] > a[j])
        	{
                temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
        		/*
				For Counting Total Number of Iterations
        		*/
                count++;
        	}
        }
    }

    printf("\n");
	printf("\nTotal Number of Iterations Needed %d", count);    
}
int main()
{
	/* 
     "Insertion Sort in C Program". This Programming Solution is belong to 
      Simple Categories in C Language. -by https://tutorialsbookmarks.com
    */	
    int number, i, j, temp;
    
    printf("Enter How Many Numbers You Want to Sorted: ");
    scanf("%d", &number);
    /*
    Array Size is equal to the numbers you entered, by using this method we can save the size.
	*/
    int a[number];
    
    printf("\n\nEnter the Numbers: ");
    /*
    Storing Numbers in an Array
	*/    
    for(i = 0; i < number; i++)
    {
        scanf("%d", &a[i]);
	}

    insertion(a, number);
    
    printf("\n\nSorting Result in Ascending order of Insertion Sort: ");
    for(i = 0; i < number; i++)
    {
        printf(" %d  ", a[i]);
    }
    
	/*
    For printing, the array insertion sort results in Descending order remove this comment
    
	printf("\n\nSorting Result in Descending order of Insertion Sort: ");
	for(i = number-1; i >= 0; i--)
    {
        printf(" %d  ", a[i]);
    } 
    */
	    
    printf("\n\n");
    return 0;
}

The Output

Step-by-Step Analysis

Let’s take an example of the Insertion sorting, As shown in the Given GIF picture. Let’s understand the given example of the output of the program Step by Step.

So this is our Input or data stored in an array, and we have to sort the array, let understand how it works.

Keynote: Always remember Insertion Sort always start with 1 index(Not 0), If your array starts with index 1 then it will start with index 2, always start with the new element of starting index of an Array or Data set.

Example input: 6 5 3 1 8 7 2 4

• So here 6 is in 0’th Index
• 5 is in 1’th Index
• 3 is in 2’th Index
• 1 is in 3’th Index
• 8 is in 4’th Index
• 7 is in 5’th Index
• 2 is in 6’th Index
• 4 is in 7’th Index

First Iterations

Now the Our array will start from Index 1 which means the array will start from the number 5, Now So we compare the second index with the first index we can see that the 5 is less than the number 6 so we just swap the number, So now our array looks like a

5 6 3 1 8 7 2 4

Second Iterations

Now Our first array index is in number 3, so again we are going to compare the number 3 to left most numbers 5 and 6 as we know that the 3 is less than the 5, and 6 so we put the number 3 before the 5 so our array will be

3 5 6 1 8 7 2 4

Third Iterations

Again repeat the same step so now compare to 1 to it left most items. So our new array will be

1 3 5 6 8 7 2 4

Forth Iterations

Repeat a previous step as we can see that 8 is greater than all left most items, so we are not going to make any changes in an array. our array will be the same

1 3 5 6 8 7 2 4

Fifth Iterations

In Fifth Iteration repeat the same step now 7 is less than 8 so we swap the position with 8. Now our new array will be

1 3 5 6 8 7 2 4

Sixth Iterations

Now we just change the number 2 location with its appropriate location.

1 2 3 5 6 7 8 4

Seventh Iterations

This is the last iteration for the array we just need to find the correct location of the number 4 and put the number in the right location.

1 2 3 4 5 6 7 8

So we need a total of 7 Iterations(for the topmost Loop) for this example, and for Nested or inner loop we need a total of 15 Total numbers of Iterations.

Frequently Asked Questions