home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / progmisc / euphor10.zip / SHELL.C < prev    next >
C/C++ Source or Header  |  1993-05-07  |  1KB  |  63 lines
  1. #include <stdio.h>
  2. #include <time.h>
  3.  
  4. #define ITERATIONS 100000
  5. #define TRUE 1
  6. #define NITEMS 50
  7.  
  8. /* index from 1 to NITEMS */
  9. int list[NITEMS+1] = 
  10.      {0, 9, 34, 14, 18, 33, 46, 11, 13, 7, 26, 22, 10, 36, 40, 2, 28, 32, 1,
  11.         23, 31, 43, 5, 24, 42, 45, 50, 16, 3, 47, 39, 21, 49, 41, 6, 19, 30,
  12.     20, 35, 44, 38, 25, 15, 27, 17, 8, 4, 29, 37, 48, 12};
  13. int x[NITEMS+1];
  14.  
  15. void shell_sort()
  16. /* Shell sort based on insertion sort */
  17. {
  18.     int i, gap, j, n; 
  19.     int tempi, tempj;
  20.  
  21.     gap = NITEMS / 4 + 1;
  22.     while (TRUE) {
  23.     for (i = gap + 1; i <= NITEMS; i++) {
  24.         tempi = x[i];
  25.         j = i - gap; 
  26.         while (TRUE) {
  27.         tempj = x[j];
  28.         if (tempi >= tempj) {
  29.             j = j + gap;
  30.             break;
  31.         }
  32.         x[j+gap] = tempj;
  33.         if (j <= gap) 
  34.             break;
  35.         j = j - gap;
  36.         }
  37.         x[j] = tempi;
  38.     }
  39.     if (gap == 1) 
  40.         return;
  41.     else
  42.         gap = gap / 4 + 1; 
  43.     }
  44. }
  45.  
  46. main()
  47. {
  48.     int t;
  49.     int i, j;
  50.  
  51.     t = clock();
  52.     for (i = 1; i <= ITERATIONS; i++) { 
  53.         for (j = 1; j <= NITEMS; j++)
  54.            x[j] = list[j];
  55.         shell_sort();
  56.     }
  57.     printf("%d iterations in %.2f seconds\n", ITERATIONS, 
  58.        (clock() - t)/(double)CLOCKS_PER_SEC);
  59.     for (i = 1; i <= NITEMS; i++)
  60.     printf("%d  ", x[i]);
  61. }
  62.  
  63.