Insertion sort program in C with explanation

by

In this tutorial, you will learn how to write Insertion sort program in c with explanation.

Before going on logic of insertion sort or program, first lets understand how insertion sort works? What is the space and time complexity of it?

What is Insertion Sort?

Insertion sort is very easy and basic sorting technique. In Insertion sort we pick first element and put it at its actual position by comparison with its right elements.

And then select next element of an array and try to place it at its actual place after comparison.

This process will continue until array gets sorted.

Lets see how its works

Suppose In array we have 4, 2, 5, 8, 1 elements.

Below I have shown how elements gets sorted using insertion sort in each steps. Bold showing sorted element and unbold is showing unsorted element.

Step 1:  4, 2, 5, 8, 1

Step 2:  2, 4, 5, 8, 1

Step 3:  2, 4, 5, 8, 1

Step 4:  2, 4, 5, 8, 1

Step 5:  1, 2, 4, 5, 8

Our approach to write insertion sort program in C

Below are the approach which we will be follow to write our program:

  • At the first we will give random number to an array which we want to sort.
  • For loop will help us to iterate the each elements of an array so that we can perform our comparison to sort array element and arrange array elements in ascending order.
  • We will select the first element of an array which is at index 0 of an array and denote it as key.
  • Now we will place it at correct position after comparison of it with right elements.
  • And will follow the same comparison process by picking one element at a time and placing it at its right place.
  • At last after the each steps we will get sorted array.
  • Our loop iteration times will depend upon the size of an array. Suppose if an array have 5 elements then 5 times for loop will be iterated.

Complexity

Best Case : O(n)

Average and Worst Case : O(n^2)

How our program will behave?

Our program will take an unsorted or sorted array as an input and will give sorted array which is in ascending order as an output.

For Example : 

suppose if i give array elements as 5, 6, 3, 1, 9

Then in output it should give 

1, 3, 5, 6, 9

Program to sort an array in ascending order using insertion sort

#include<stdio.h>
#include<conio.h>
void main(){
    int arr[100],i,j,n,key;
    printf("This Program is for Insertion Sort n");
    printf("Enter the size of array:n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: n",n);
    for(i=0;i<n;i++){
	    scanf("%d",&arr[i]);
    }
    printf("before sorting:n");
    for(i=0;i<n;i++){
        printf("%d t",arr[i]);
    }
    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;
	}
    printf("n");
    printf("after sorting:n");
    for(i=0;i<n;i++){
	    printf("%dt",arr[i]);
	}
    getch();
}

Output:

insertion sort program in c

Explanation of above program to sort an array using insertion sort

  • In the above program we have one array arr of int type, and 4 variables i, j, n, key.
  • Now using for loop we will take input from user to put in array. And Also one for loop is to print original arrangement of an array before sorting.
  • key variable is used to store one element which we want to place at its original place.
  • while loop is to validate the condition. And according to condition it will help to assign at correct index of an array so that our final result would be a sorted array.

Leave a Comment