Insertion Sort in C – Pseudocode Code, Explanation, Real Life Examples

1
99
How Insertion Sorts Works GIF Example

Insertion Sort in C: Insertion Sort is the very simple and adaptive sorting techniques, 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 what 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
  • Analaysis 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 another sorting technique (Selection, Bubble, Merge, Heap, QuickSort, Radix, Counting, Bucket, ShellSort, and Comb Sort).

It’s very useful with 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 in just 3 steps and the optimize version in just 5 steps.

Insertion Sort Bar Code Solver GIF

Advantages of Insertion Sort

There are many advantages, below is the 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 elements which are equal.

Disadvantages of Insertion Sort

As we know that all sorting algorithms have some disadvantage 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 played and all of them have 13 cards, after that they arranged the card according to colour, type, of ascending or descending order, it’s totally depends on the players habits but one thing is clear they pick a card from the 13 and set the card in the correct position.

Playing Card

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.ComplexityTimeSpace
1Best-CaseО(n)
2Average CaseО(n^2)
4Worst-CaseО(n^2)
5Space ComplexityО(n) Total, O(1) Auxiliary

All the solutions are tested on Dev-C++ and online compilers, If you still face any issue 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

output of C Program

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

output of C Program Using While Loop

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

C Program Output Using Functions

Step by Step Analysis

Let’s take an example for the Insertion sorting, As shown in 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.

How Insertion Sorts Works GIF Example

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

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 clearly 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 previously step again as we can see that 8 is greater then 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 Iterations repeat the same step now 7 is less than the 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 on the right location.

1 2 3 4 5 6 7 8

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

Frequently Asked Questions

Can you implement insertion sort for sorting linked lists?

The answer is, yes, you can implement insertion sort on a linked list.

What will be time complexity of insertion sort if the array is already sorted?

O(n), If the array is already sorted.

What is the time complexity of insertion sort for an unsorted list?

O(n^2), Worst-case and average-case complexity are the same.

What are the Arithmetic Operators in C?

Please see this guide for a complete explanation for arithmetic operators in C language

1 COMMENT

  1. Bounce rate.
    Network traffic to boost ranks and exposure.

    NEW! Now you can choose the Country you want the traffic to come from, as well.

    Supercharge Your SEO And Boost Your Alexa Ranking with 1 Million unique Visitors Traffic sent Within 1 Month. Available only Here. Cheapest Offer On the Internet And Exclusively Available on Monkey Digital

    Read More details about our great offer:
    https://monkeydigital.co/product/network-traffic-offer/

    Thanks and regards
    Mike
    Monkey Digital
    monkeydigital.co@gmail.com

LEAVE A REPLY

Please enter your comment!
Please enter your name here