home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgLangD.iso / TC-300 / BIN / ASSIGN1.BAK < prev    next >
Text File  |  1994-04-14  |  4KB  |  201 lines
  1. /* A program to sort a range of numbers with Insertion
  2.    and Quicksort, check their sorting time and prompt
  3.    the result on the screen */
  4.  
  5.  
  6. /* use header file*/
  7. #include <stdio.h>
  8. #include <iostream.h>
  9. #include <stdlib.h>
  10. #include <values.h>
  11. #include <time.h>
  12. #include <string.h>
  13. #include <conio.h>
  14.  
  15. /* define variable */
  16. const int max=29000;
  17. int list[max];
  18. FILE *fp;
  19. clock_t start,end;
  20. char any1[8];
  21.  
  22. /* Insertion sort module */
  23. void insertion(int min1,int max1)
  24. {
  25.     int a,b,v;
  26.  
  27.     for(a=min1;a<=max1;a++)
  28.     {
  29.        v = list[a];
  30.        b = a;
  31.        do
  32.        {
  33.        list[b] = list[b-1];
  34.        b = b - 1;
  35.        }  while(list[b-1] > v);
  36.        list[b] = v;
  37.     }
  38. }
  39.  
  40. /* sort partitioning element */
  41. void sorthree(int x,int y,int z)
  42. {
  43. int temp;
  44.  
  45. if (list[x] > list[y])
  46. {
  47.    temp = list[x];
  48.    list[x] = list[y];
  49.    list[y] = temp;
  50. }
  51. if (list[z] < list[x])
  52. {
  53.    temp = list[x];
  54.    list[x] = list[z];
  55.    list[z] = temp;
  56.    temp = list[y];
  57.    list[y] = list[z];
  58.    list[z] = temp;
  59. }
  60. if ((list[z] > list[x]) && (list[z] < list[y]))
  61. {
  62.    temp = list[y];
  63.    list[y] = list[z];
  64.    list[z] = temp;
  65. }
  66. }
  67.  
  68. /* Quicksort module */
  69. void quicksort(int min2,int max2)
  70. {
  71. int v,t,i,j,q;
  72.  
  73. if ((max2-min2) > 9)
  74. {
  75.    int m = (max2-min2+1)/2;
  76.    sorthree(min2,m,max2);
  77.    max2=max2-1;
  78.    q = list[m];
  79.    list[m] = list[max2];
  80.    list[max2] = q;
  81.  
  82.    v = list[max2];
  83.    i = min2+1;
  84.    j = max2-1;
  85.    do
  86.    {
  87.       do
  88.       {
  89.      i=i+1;
  90.       } while (list[i] < v);
  91.       do
  92.       {
  93.      j=j-1;
  94.       } while (list[j] > v);
  95.       t = list[i];
  96.       list[i] = list[j];
  97.       list[j] = t;
  98.    }  while (i<j);
  99.    list[j]=list[i];
  100.    list[i]=list[max2];
  101.    list[max2]=t;
  102.    quicksort(min2,i-1);
  103.    quicksort(i+1,max2);
  104.  }
  105. else
  106.  insertion(min2,max2);
  107. }
  108.  
  109.  
  110. /* main program */
  111. void main()
  112. {
  113. int i,j,k,min,max1;
  114. char any2[8];
  115.  
  116. clrscr();
  117. cout << "Enter a file name to store data :";
  118. cin >> any1;                                  /* input data file name on */
  119. cout << '\n' << "Generating file...waits\n\n";/*   screen */
  120.  
  121. fp = fopen(any1,"w");
  122.     for(j=0;j<max/200;j++)
  123.     {
  124.        for(i=0;i<200;i++)    /* write random values to file */
  125.        {
  126.        k = rand();
  127.        fprintf(fp,"%d\n",k);
  128.        }
  129.     }
  130. fclose(fp);
  131.  
  132. fp = fopen(any1,"r");
  133.     i = 0;
  134.     while(fscanf(fp,"%d\n",&k) != EOF)
  135.     {
  136.       list[i] = k;  /* read values from file and assign to an array */
  137.       i = i + 1;
  138.     }
  139. fclose(fp);
  140. min = 0;
  141. max1 = max;
  142. max1=max1-1;
  143. cout << "Sorting with Quicksort... waits" << '\n';
  144. start = clock();
  145. quicksort(min,max1);   /* sort an unsorted list with quicksort */
  146. end=clock();
  147. float result = (end-start)/CLK_TCK;
  148. cout << "The time needs to sort " << max
  149.      << " numbers in Quciksort is : " << result << " second(s)" << "\n\n";
  150.  
  151.  
  152. cout << "Enter an output file for Quicksort : ";
  153. cin >> any2;
  154.  
  155. fp = fopen(any2,"w");
  156.   for(i=0;i<max;i++)
  157.   {                   /* write the output from quicksort and put them */
  158.       k = list[i];    /*to a file */
  159.       fprintf(fp,"%d\n",k);
  160.   }
  161. fclose(fp);
  162.  
  163. fp = fopen(any1,"r");
  164.     i = 0;
  165.     while(fscanf(fp,"%d\n",&k) != EOF)
  166.     {
  167.       list[i] = k;
  168.       i = i + 1;
  169.     }
  170. fclose(fp);
  171. cout << "\nSorting with Insertion Sort... waits" << '\n';
  172. start = clock();
  173. insertion(0,max);   /* sort an unsorted list with insertion sort */
  174. end=clock();
  175. result = (end-start)/CLK_TCK;
  176. cout << "The time needs to sort " << max
  177.      << " numbers in Insertion is : " << result << " second(s)" << "\n\n";
  178.  
  179. cout << "Sort an already sorted array again with Quicksort..." << '\n';
  180. min = 0;
  181. max1 = max;
  182. max1=max1-1;
  183. start = clock();
  184. quicksort(min,max1);  /* sort an already sort list with quicksort */
  185. end=clock();
  186. result = (end-start)/CLK_TCK;
  187. cout << "The time needs to sort " << max
  188.      << " numbers in Quicksort is : " << result << " second(s)" << "\n";
  189.  
  190. cout << "Sort an already sorted array again with Insertion sort..." << '\n';
  191. start = clock();
  192. insertion(0,max);   /* sort an already list with insertion sort */
  193. end=clock();
  194. result = (end-start)/CLK_TCK;
  195. cout << "The time needs to sort " << max
  196.      << " numbers in Insertion sort is : " << result << " second(s)" << '\n';
  197. }
  198.  
  199.  
  200.  
  201.