lang/C/sorting.and.searching.cormen.algo/src/shl.txt

   1 /* shell sort */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 typedef int T;          /* type of item to be sorted */
   7 typedef int tblIndex;   /* type of subscript */
   8
   9 #define compGT(a,b) (a > b)
  10
  11 void shellSort(T *a, tblIndex lb, tblIndex ub) {
  12     tblIndex i, j;
  13     unsigned int n;
  14     int t;
  15
  16     static const unsigned int h[] = {
  17         1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929,
  18         16001, 36289, 64769, 146305, 260609, 587521, 1045505,
  19         2354689, 4188161, 9427969, 16764929, 37730305, 67084289,
  20         150958081, 268386305, 603906049, 1073643521, 2415771649U
  21     };
  22
  23     /* find t such that 3*h[t] >= n */
  24     n = ub - lb + 1;
  25     for (t = 0; 3*h[t] < n; t++);
  26
  27     /* start with h[t-1] */
  28     if (t > 0) t--;
  29
  30     while (t >= 0) {
  31         unsigned int ht;
  32
  33         /* sort-by-insertion in increments of h */
  34         ht = h[t--];
  35         for (i = lb + ht; i <= ub; i++) {
  36             T tmp = a[i];
  37             for (j = i-ht; j >= lb && compGT(a[j], tmp); j -= ht)
  38                 a[j+ht] = a[j];
  39             a[j+ht] = tmp;
  40         }
  41     }
  42 }
  43
  44 void fill(T *a, tblIndex lb, tblIndex ub) {
  45     tblIndex i;
  46     srand(1);
  47     for (i = lb; i <= ub; i++) a[i] = rand();
  48 }
  49
  50 int main(int argc, char *argv[]) {
  51     tblIndex maxnum, lb, ub;
  52     T *a;
  53
  54     /* command-line:
  55      *
  56      *   shl maxnum
  57      *
  58      *   shl 2000
  59      *       sort 2000 records
  60      */
  61
  62     maxnum = atoi(argv[1]);
  63     lb = 0; ub = maxnum - 1;
  64     if ((a = malloc(maxnum * sizeof(T))) == 0) {
  65         fprintf (stderr, "insufficient memory (a)\n");
  66         exit(1);
  67     }
  68
  69     fill(a, lb, ub);
  70     shellSort(a, lb, ub);
  71
  72     return 0;
  73 }