Home » Data Structure

Implementing insertion sort using C

In this article, we are going to learn what insertion is sorting and how to implement Insertion Sort?
Submitted by Manu Jemini, on January 24, 2018

When we say sorting it means serializing a collection of data inside any the collections like arrays, linked list etc. There is one good reason for implementing sorting on any collection is that it makes the searching very fast as compared to the collection which is unsorted. Now, this is not true for every test case but on an average, it is so. Element and compare it with the 0th element, if the 1st element is smaller than the 0th element that means we will swap both of them.

Image source: http://www.cprogramto.com/wp-content/uploads/2014/05/insertion-sort-11.png

Similarly, we will do this for 2^nd element with 0^th index if is bigger than the 0^th element it will move to the next element and compare it.

This is very simple and slow as compared to the divide and conquer technique based sorting.

C program to implement insertion sort

#include <stdio.h>
#define MAX 20

void insertion(int arr[],int n)
{ 
	int j,k,i;
	/*Insertion sort*/
	for(j=1;j<n;j++)
	{	
		k=arr[j]; /*k is to be inserted at proper place*/
		for(i=j-1;i>=0 && k<arr[i];i--)
		{	
			arr[i+1]=arr[i];
		}
		arr[i+1]=k;
	}
}

int main()
{
	int arr[MAX],i,n;
	printf("Enter the number of elements : ");
	scanf("%d",&n);
	for (i = 0; i < n; i++)
	{
		printf("Enter element %d : ",i+1);
		scanf("%d", &arr[i]);
	}

	printf("Unsorted list is :\n");
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
	
	insertion(arr,n);
	
	printf("Sorted list is :\n");
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
	
	return 0;
}/*End of main()*/

Output