Written by Sai Sandeep Thota on December 26, 2012 in C > Programming

Insertion Sort C Program Code with Explanation

GET ALERTS:

Get our Latest updates delivered to your mailbox!

Insertion sort is one of the three Basic Sorting techniques. In this article, we are going to explain the Insertion Sort C Code. Insertion sort is divided into two segments, They are Sorted list and Unsorted list. On each pass the first element of the unsorted list is picked and is transferred into the sorted list by inserting at appropriate position. If we have n elements, then it will take (n-1) passes to complete the sorting process.

Incase, If you missed the first two Basic Sorting techniques which we have discussed earlier. Here they are:

  1. Bubble Sort
  2. Selection Sort

For instance, Take card players. They arrange the cards in a sequential order.

For example:
1: 23 |  78  45  60  15
2: 23  78  |  45  60  15
3: 23  45  78  |  60  15
4: 23  45  60  78  |  15
5: 15  23  45  60  78  |

As we have discussed earlier “|” divides the two segments. Elements on the left are sorted and on the right are unsorted.

Insertion sort will have a Time Complexity of O(n) in Best Case and O(n²) in Average and Worst cases. Take a look at the program of Insertion Sort below:

/* C Program to Implement Insertion Sort */
#include
#include
#define max 50
void inssort(int, int[]);

void inssort(int n, int data[])
{
	int index, i, j;
	printf("\nSorted List is:\n");
	for(i=1;i<=n;i++) 	{ 		index=data[i]; 		for(j=i;j>0&&data[j-1]>index;j--)
			data[j]=data[j-1];
		data[j]=index;
	}
	for(i=1;i<=n;i++)

		printf("%d\t",data[i]);

}

void main()
{
	int i, size, data[max];
	clrscr();
	printf("\nEnter no of Elements:");
	scanf("%d",&size);
	printf("\nEnter Elements:");
	for(i=1;i<=size;i++)
		scanf("%d",&data[i]);
	printf("\nUnsorted data:\n");
	for(i=1;i<=size;i++)
		printf("%d\t",data[i]);
	inssort(size, data);
	getch();
}

Output:
InsertionSort-output

{ 0 comments… add one now }

Leave a Comment

Previous post:

Next post: