Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.




Algorithm

INSERTION-SORT(A)
1. for j = 2 to A.length
2. key = A[j]
3. // Insert A[j] into the sorted sequence A[1...j-1]
4. i = j - 1
5. while i > 0 and A[i] > key
6. A[i+1] = A[i]
7. i = i - 1
8. A[i+1] = key



Insertion Sort

#include<stdio.h>
#include<conio.h>
void main()
{
	int A[20],n,Temp,i,j;
	clrscr();
	printf("\n\t\t\t-----INSERTION SORT-----\n\n");
	printf("\n\n ENTER THE NUMBER OF TERMS...: ");
	scanf("%d",&n);
	printf("\n ENTER THE ELEMENTS OF THE ARRAY...:\n");
	for(i=0; i < n;i++)
	{
		scanf("%d", &A[i]);
	}
	for(i=1; i< n; i++)
	{
		Temp = A[i];
		j = i-1;
		while(Temp < A[j] && j>=0)
		{
			A[j+1] = A[j];
			j = j-1;
		}
		A[j+1] = Temp;
	}
	printf("\n\t\t\t-------INSERTION SORTED ELEMENTS------\n\n");
	printf("\nTHE ASCENDING ORDER LIST IS...:");
	for(i=0; i < n; i++)
	{
		printf("\t%d", A[i]);
	}
	getch();
}
  



OUTPUT





Analysis Of Insertion

Class Sorting algoritdm
Data structure Array
Worst case performance О(n2)
Best case performance O(n)
Average case performance О(n2) comparisons
Worst case space complexity О(n) total, O(1) auxiliary




Quantitative Aptitude
Reasoning
Programming
Interview