Program to sort a range of numbers with Insertion and Quicksort, check their sorting time and prompt the result on the screen

/* A program to sort a range of numbers with Insertion

   and Quicksort, check their sorting time and prompt

   the result on the screen */





/* use header file*/

#include 

#include 

#include 

#include 

#include 

#include 

#include 



/* define variable */

const int max=29000;

int list[max];

FILE *fp;

clock_t start,end;

char any1[8];



/* Insertion sort module */

void insertion(int min1,int max1)

{

    int a,b,v;



    for(a=min1;a<=max1;a++)

    {

       v = list[a];

       b = a;

       do

       {

       list[b] = list[b-1];

       b = b - 1;

       }  while(list[b-1] > v);

       list[b] = v;

    }

}



/* sort partitioning element */

void sorthree(int x,int y,int z)

{

int temp;



if (list[x] > list[y])

{

   temp = list[x];

   list[x] = list[y];

   list[y] = temp;

}

if (list[z] < list[x])

{

   temp = list[x];

   list[x] = list[z];

   list[z] = temp;

   temp = list[y];

   list[y] = list[z];

   list[z] = temp;

}

if ((list[z] > list[x]) && (list[z] < list[y]))

{

   temp = list[y];

   list[y] = list[z];

   list[z] = temp;

}

}



/* Quicksort module */

void quicksort(int min2,int max2)

{

int v,t,i,j,q;



if ((max2-min2) > 9)

{

   int m = (max2-min2+1)/2;

   sorthree(min2,m,max2);

   max2=max2-1;

   q = list[m];

   list[m] = list[max2];

   list[max2] = q;



   v = list[max2];

   i = min2+1;

   j = max2-1;

   do

   {

      do

      {

     i=i+1;

      } while (list[i] < v);

      do

      {

     j=j-1;

      } while (list[j] > v);

      t = list[i];

      list[i] = list[j];

      list[j] = t;

   }  while (i   list[j]=list[i];

   list[i]=list[max2];

   list[max2]=t;

   quicksort(min2,i-1);

   quicksort(i+1,max2);

 }

else

 insertion(min2,max2);

}





/* main program */

void main()

{

int i,j,k,min,max1;

char any2[8];



clrscr();

cout << "Enter a file name to store data :";

cin >> any1;                                  /* input data file name on */

cout << '\n' << "Generating file...waits\n\n";/*   screen */



fp = fopen(any1,"w");

    for(j=0;j    {

       for(i=0;i<200;i++)    /* write random values to file */

       {

       k = rand();

       fprintf(fp,"%d\n",k);

       }

    }

fclose(fp);



fp = fopen(any1,"r");

    i = 0;

    while(fscanf(fp,"%d\n",&k) != EOF)

    {

      list[i] = k;  /* read values from file and assign to an array */

      i = i + 1;

    }

fclose(fp);

min = 0;

max1 = max;

max1=max1-1;

cout << "Sorting with Quicksort... waits" << '\n';

start = clock();

quicksort(min,max1);   /* sort an unsorted list with quicksort */

end=clock();

float result = (end-start)/CLK_TCK;

cout << "The time needs to sort " << max

     << " numbers in Quciksort is : " << result << " second(s)" << "\n\n";





cout << "Enter an output file for Quicksort : ";

cin >> any2;



fp = fopen(any2,"w");

  for(i=0;i  {                   /* write the output from quicksort and put them */

      k = list[i];    /*to a file */

      fprintf(fp,"%d\n",k);

  }

fclose(fp);



fp = fopen(any1,"r");

    i = 0;

    while(fscanf(fp,"%d\n",&k) != EOF)

    {

      list[i] = k;

      i = i + 1;

    }

fclose(fp);

cout << "\nSorting with Insertion Sort... waits" << '\n';

start = clock();

insertion(0,max);   /* sort an unsorted list with insertion sort */

end=clock();

result = (end-start)/CLK_TCK;

cout << "The time needs to sort " << max

     << " numbers in Insertion is : " << result << " second(s)" << "\n\n";



cout << "Sort an already sorted array again with Quicksort..." << '\n';

min = 0;

max1 = max;

max1=max1-1;

start = clock();

quicksort(min,max1);  /* sort an already sort list with quicksort */

end=clock();

result = (end-start)/CLK_TCK;

cout << "The time needs to sort " << max

     << " numbers in Quicksort is : " << result << " second(s)" << "\n";



cout << "Sort an already sorted array again with Insertion sort..." << '\n';

start = clock();

insertion(0,max);   /* sort an already list with insertion sort */

end=clock();

result = (end-start)/CLK_TCK;

cout << "The time needs to sort " << max

     << " numbers in Insertion sort is : " << result << " second(s)" << '\n';

}

Related Links :