Design and Analysis of Algorithms

Go Back to List

Program to sort list using insertion sort.

 

#include<iostream.h>
#include<conio.h>
void main()
{
int a[20],i,ptr,n,temp;
clrscr();
cout<<"\nHow many numbers you want to enter: ";
cin>>n;
cout<<"\n Enter the "<<n<<" numbers:";
a[0]=-1;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=2;i<=n;i++)
{
temp=a[i];
ptr=i-1;
while(temp<a[ptr])
{
a[ptr+1]=a[ptr]; //Moves element forward
ptr--;
}
a[ptr+1]=temp; //Inserts element in proper place
}
cout<<"\nSorted list is:";
for(i=1;i<=n;i++)
cout<<" "<<a[i];
getch();
}





 

Output:

How many numbers you want to enter: 5

Enter the 5 numbers:12
11
21
13
4

Sorted list is: 4 11 12 13 21

Analysis of Insertion Sort:

Worst case:
It occurs when the array is in reverse order and inner loop must use maximum number i-1 of comparisons, therefore,
f(n) = 1+2+ … +(n-1) = n(n-1)/2 = O(n2)
Average case
On the average, there will be approximately (k-1)/2 comparisons in the inner loop, hence,
f(n) = ½ + 2/2 + … +(n-1)/2 = n(n-1)/4 = O(n2)

So, the complexity is for both worst case and average case is O(n2)

 

If any of you want  to submit your programs and contribute to site please mail us at:

citysuvidha@gmail.com

  Click here to have a look at  List of programs

You can download all the programs in a zip file also. For this you have to do one thing. Just register at the citysuvidha forum  and start any thread of any topic.  Once you start the thread and put your request, admin will automatically send you the desired zip file.