My Project - Video Waker Alarm
Get Video alarm on Google Play

C program for Insertion Sort


C program for Insertion Sort. Insertion sort is one of the simple-stable-in place Sorting Algorithm which is efficient when applied over small set of data. While insertion sort takes more time to perform sorting over large list i.e less efficient for large set of data, as compare to other sorting algorithm. Insertion sort reminds one of Selection sort. You can also see other sorting algorithm implementation like, Heap sort, bubble sort etc.

Insertion sort:

How will you sort your mark-sheet arranged in pile, according to marks obtained? Well very easy, a very practical approach is to first, compare first and second marks and put them in order or correct position by inserting, now take out third one and compare it with second and first and put it in right position. Now take out fourth and so on. This approach of inserting element in a sorted list is called as Insertion sort. Here is Pseudocode:

Pseudocode for insertion sort algorithm:

for i <- 1 to n-1 (A[0....n])
	Elem <- A[i]
	j <- i-1
	while j > 0 && A[j-1] > Elem
		A[j] <- A[j-1]
		j <- j-1
	A[j] <- x

C program for Insertion Sort

#include <stdio.h>

//Insertion Sort function to Sort Integer array list
int *insertionSort(int array[],int n)
{
    int j,temp,i;
    
    //Iterate start from second element 
    for (i = 1; i < n; i++)
    {
        j = i;
        //Iterate and compare till it satisfies condition 
        while ( j > 0 && array[j] < array[j-1])
        {
            //Swaping operation
            temp = array[j];
            array[j]   = array[j-1];
            array[j-1] = temp;
            j--;
        }
    }
    //return Sorted array
    return array;
}

int main()
{
    //declaring variables
    int array[1000],n,i;
    
    //Number of elements in array form user input
    printf("Enter the number of element you want to Sort : ");
    scanf("%d",&n);

    //code to ask to enter elements from user equal to n
    printf("Enter Elements in the list : ");
    for(i = 0; i < n; i++)
    {
        scanf("%d",&array[i]);
    }

    //calling insertionSort function defined above and gettting
    //sorted array in sortArray variable
    int *sortArray = insertionSort(array,n);
    
    //print sorted array
    for(i = 0; i < n; i++ )
    {
        printf("%d\t",sortArray[i]);
    }
}

Output of C program for Insertion Sort:

C program for Insertion Sort
C program for Insertion Sort

Example of Insertion sort:

Still getting problem or confused how insertion sort algorithm works, then see the images below, demonstrating the operation performed to sort the array:

Let us take integer array A = 18,9,5,12,1

C program for Insertion Sort Example
Insertion Sort Example
C program for Insertion Sort Example
Insertion Sort Example
C program for Insertion Sort Example
Insertion Sort Example
C program for Insertion Sort Example
Insertion Sort Example
C program for Insertion Sort
C program for Insertion Sort

Hope this example is helpful. Do comment below with your experience, problem or code. Your comment is very valuable to us.