Friday, October 4, 2013

comparison of running time of merge sort and insertion sort

#include
#include
using namespace std;
#define MAXSIZE 200000
class sort{
int b[MAXSIZE + 1];
public:
void insertion_sort(int a[],int n)
{
for(int i=1;i{
   int j;
   int key = a[i];
  for(j=i-1;j>=0;j--)
  {
   if(a[j]<=key)
   break;
   a[j+1]=a[j];  
  }
  a[j+1]=key;
}
}
public:
void merge_sort(int a[],int n)
{
 mergesort(a,0,n-1);
}

void mergesort(int a[],int i,int j)
{
    int mid;
    if(i    {
        mid = (i+j)/2;
        mergesort(a,i,mid);
        mergesort(a,mid+1,j);
        merge(a,i,mid,j);
    }
}

void merge(int a[],int low,int mid,int high)
{
    int h,i,j,k;
    h=low;
    i=low;
    j=mid+1;
    while(h<=mid && j<= high)
    {
        if(a[h] <= a[j])
        b[i]=a[h++];
        else
        b[i]=a[j++];
        i++;
       
    }
    if(h>mid)
    {
        for(k=j;k<=high;k++)
        b[i++]=a[k];
     
    }
    else
    {
       for(k=h;k<=mid;k++)
        b[i++]=a[k];
     
    }
    for(k=low;k<=high;k++)
    {
        a[k]=b[k];
    }
}
};
int main()
{
int a[MAXSIZE];
int b[MAXSIZE];
int temp = MAXSIZE;
for(int i=0;i{
  //int temp = random()%10000 + 1;
  a[i]=temp;
  b[i]=temp;
  temp= temp-1;
}
sort s;
int t1,t2,t3;
t1=clock();
s.merge_sort(b,MAXSIZE);
t2=clock();
s.insertion_sort(a,MAXSIZE);
t3=clock();
int size = MAXSIZE;
cout<<"The time for mergesort for n ="<< size << " is"<< t2-t1<<"\n";
cout<<"The time for insertion sort for n = "<< size <<"is "<//cout<<"\n"<//for(int i=0;i//{
//cout<//}
//cout<//for(int i=0;i//{
//cout<//}
return 0;
}