PROGRAM TO ANALYSE VARIOUS SORTING TECHNIQUES.

#include<iostream.h>         //HEADER FILES
#include<time.h>
#include<fstream.h>
#include<math.h>

fstream file;
int record[30000],copy[30000];            //TO STORE DATA
long comp=0,avgcomp;
long swp,avgswp;
long avgtime;

void bubblesort(int x[],int n)           //BUBBLE SORT
{
int hold,j,i;
int swapped=1;
comp=swp=0;
for(i=0;i<n-1&&swapped==1;i++)
{
swapped=0;
for(j=0;j<n-i;j++)
{
comp++;
if(x[j]>x[j+1])
{
swapped=1;
swp++;
hold=x[j];
x[j]=x[j+1];
x[j+1]=hold;
}
}
}
}

void insertsort(int x[],int n)               //INSERTION SORT
{
int i,j,temp;
comp=swp=0;
for(i=0;i<n;i++)
{
temp=x[i];
for(j=i-1;j>=0&&temp<x[j];j--)
{
comp++;
swp++;
x[j+1]=x[j];
}
x[j+1]=temp;
swp++;
}
}

void selectsort(int x[],int n)          //EXCHANGE SORT
{
int i,j,index,min;
comp=swp=0;
for(i=0;i<n-1;i++)
{
min=x[i];
index=i;
for(j=1+i;j<n;j++)
{
comp++;
if(x[j]<min)
{
min=x[j];
index=j;
}
}
if(index!=i)
{
x[index]=x[i];
x[i]=min;
swp++;
}
}
}

void shellsort(int x[], int n)         //SHELL SORT - SHELL'S INCREMENTS
{
int i, j,k, increment, temp;
swp=comp=0;
increment = n/2;
while (increment > 0)
{
for (i=0;i<increment;i++)
{
for(j=0;j<n;j+=increment)
{
temp=x[j];
for(k=j-increment;k>=0&&temp<x[k];k-=increment)
{
comp++;
swp++;
x[k+increment]=x[k];
}
x[k+increment]=temp;
swp++;
}
}
comp++;
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}

void hibbardsort(int x[], int n)       //SHELL SORT - HIBBARD'S INCREMENTS
{
int i, j,k, increment, temp;
swp=comp=0;
int val;
val=log(n+1)/log(2);
increment =pow(2,val)-1;
while (increment > 0)
{
for (i=0;i<increment;i++)
{
for(j=0;j<n;j+=increment)
{
temp=x[j];
for(k=j-increment;k>=0&&temp<x[k];k-=increment)
{
comp++;
swp++;
x[k+increment]=x[k];
}
x[k+increment]=temp;
swp++;
}
}
comp++;
val--;
if(increment!=1)
increment=pow(2,val)-1;
else
increment = 0;
}
}

void sedgewicksort(int x[], int n)     //SHELL SORT - SEDGEWICK'S INCREMENTS
{
int i, j,k, increment, temp;
swp=comp=0;
int val,incrmnt[]={16001,8929,3905,2161,929,505,209,109,41,19,5,1};
val=0;
increment =incrmnt[val];
while (increment > 0)
{
for (i=0;i<increment;i++)
{
for(j=0;j<n;j+=increment)
{
temp=x[j];
for(k=j-increment;k>=0&&temp<x[k];k-=increment)
{
comp++;
swp++;
x[k+increment]=x[k];
}
x[k+increment]=temp;
swp++;
}
}
comp++;
val++;
if(incrmnt[val-1]!=1)
increment=incrmnt[val];
else
increment = 0;
}
}

void main()                  //EXECUTION STARTS HERE
{
int i,j,k,l,valid;
file.open("records.txt",ios::in);
for(i=0;i<30000;i++)          //READ RECORDS
file>>record[i];
file.close();

long p,q,r;
cout<<"\n\n WAIT..........................";

file.open("bubble.txt",ios::out);         //BUBBLE SORT
for(k=1;k<=300;k++)
{
valid=100*k;
r=0.0;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
bubblesort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("select.txt",ios::out);       //EXCHANGE SORT
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
selectsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("insert.txt",ios::out);         //INSERTION SORT
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
insertsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("shell.txt",ios::out);    //SHELL SORT - SHELL'S INCREMENTS
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
shellsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("hibbard.txt",ios::out); //SHELL SORT - HIBBARD'S INCREMENTS
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
hibbardsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("sedgewick.txt",ios::out);   //SHELL SORT - SEDGEWICK'S INCREMENTS
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
sedgewicksort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s