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

   1 /* qsort() */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <limits.h>
   6
   7 typedef int T;          /* type of item to be sorted */
   8
   9 #define MAXSTACK (sizeof(size_t) * CHAR_BIT)
  10
  11 #define exchange(a, b, size) \
  12 { \
  13     size_t s; \
  14     int *ai, *bi; \
  15     char *ac, *bc; \
  16     ai = (int *)a; \
  17     bi = (int *)b; \
  18     for (s = sizeof(int); s <= size; s += sizeof(int)) { \
  19         int t = *ai; \
  20         *ai++ = *bi; \
  21         *bi++ = t; \
  22     } \
  23     ac = (char *)ai; \
  24     bc = (char *)bi; \
  25     for (s = s - sizeof(int) + 1; s <= size; s++) { \
  26         char t = *ac; \
  27         *ac++ = *bc; \
  28         *bc++ = t; \
  29     } \
  30 }
  31
  32 void qsort(void *base, size_t nmemb, size_t size,
  33         int (*compar)(const void *, const void *)) {
  34     void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
  35     int sp;
  36     unsigned int offset;
  37
  38     /********************
  39      *  ANSI-C qsort()  *
  40      ********************/
  41
  42     lbStack[0] = (char *)base;
  43     ubStack[0] = (char *)base + (nmemb-1)*size;
  44     for (sp = 0; sp >= 0; sp--) {
  45         char *lb, *ub, *m;
  46         char *P, *i, *j;
  47
  48         lb = (char *)lbStack[sp];
  49         ub = (char *)ubStack[sp];
  50
  51         while (lb < ub) {
  52
  53             /* select pivot and exchange with 1st element */
  54             offset = (ub - lb) >> 1;
  55             P = lb + offset - offset % size;
  56             exchange (lb, P, size);
  57
  58             /* partition into two segments */
  59             i = lb + size;
  60             j = ub;
  61             while (1) {
  62                 while (i < j && compar(lb, i) > 0) i += size;
  63                 while (j >= i && compar(j, lb) > 0) j -= size;
  64                 if (i >= j) break;
  65                 exchange (i, j, size);
  66                 j -= size;
  67                 i += size;
  68             }
  69
  70             /* pivot belongs in A[j] */
  71             exchange (lb, j, size);
  72             m = j;
  73
  74             /* keep processing smallest segment, and stack largest */
  75             if (m - lb <= ub - m) {
  76                 if (m + size < ub) {
  77                     lbStack[sp] = m + size;
  78                     ubStack[sp++] = ub;
  79                 }
  80                 ub = m - size;
  81             } else {
  82                 if (m - size > lb) {
  83                     lbStack[sp] = lb;
  84                     ubStack[sp++] = m - size;
  85                 }
  86                 lb = m + size;
  87             }
  88         }
  89     }
  90 }
  91
  92 void fill(T *lb, T *ub) {
  93     T *i;
  94     srand(1);
  95     for (i = lb; i <= ub; i++) *i = rand();
  96 }
  97
  98 int Comp(const void *a, const void *b) { return *(T *)a - *(T *)b; }
  99
 100 int main(int argc, char *argv[]) {
 101     int maxnum;
 102     int *a, *lb, *ub;
 103
 104     /* command-line:
 105      *
 106      *   qsort maxnum
 107      *
 108      *   qsort 2000
 109      *       sorts 2000 records
 110      *
 111      */
 112
 113     maxnum = atoi(argv[1]);
 114     if ((a = malloc(maxnum * sizeof(T))) == 0) {
 115         fprintf (stderr, "insufficient memory (a)\n");
 116         exit(1);
 117     }
 118     lb = a;  ub = a + maxnum - 1;
 119
 120     fill(lb, ub);
 121     qsort(a, maxnum, sizeof(T), Comp);
 122     return 0;
 123 }