home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 161_01 / qsortpro.c < prev    next >
C/C++ Source or Header  |  1985-08-29  |  3KB  |  105 lines
  1. /* qsort - sort array a (dimension n) using quicksort
  2.  * based on Bentley, CACM April 84
  3.  * Comments use notation A[i], a (fictitious) array of things
  4.  * that are of size elt_size.
  5.  */
  6. #include "local.h"
  7. /* swapfn - swap  elt_size bytes  a <--> b (internal routine) 
  8.  */
  9. void swapfn(a, b, elt_size)
  10.     register char *a;    /* pointer to one element of A */
  11.     register char *b;    /* pointer to another element of A */
  12.     size_t elt_size;    /* size of each element */
  13.     {
  14.     register size_t i;
  15.     char tmp;
  16.  
  17.     LOOPDN(i, elt_size)
  18.         {
  19.         SWAP(*a, *b, tmp);
  20.         ++a, ++b;
  21.         }
  22.     }                                                                                                                                          /*
  23. .PE
  24. .PS 25
  25. /* iqsort - internal quicksort routine */
  26. void iqsort(p_lo, p_hi, elt_size, cmpfn)
  27.     char *p_lo;            /* ptr to low element of (sub)array */
  28.     char *p_hi;            /* ptr to high element of (sub)array */
  29.     size_t elt_size;    /* size of each element */
  30.     int (*cmpfn)();        /* comparison function ptr */
  31.     {
  32.     char *p_mid;                /* pointer to middle element */
  33.     register char *p_i;            /* pointer to A[i] */
  34.     register char *p_lastlo;    /* pointer to A[lastlo] */
  35.  
  36.     if (p_hi <= p_lo)            /* is partition trivial? */
  37.         return;
  38.     p_mid = p_lo + ((((p_hi - p_lo) / elt_size) / 2) * elt_size);
  39.     swapfn(p_lo, p_mid, elt_size);    /* pick the middle element as pivot */
  40.     p_lastlo = p_lo;
  41.     for (p_i = p_lo + elt_size;  p_i <= p_hi; p_i += elt_size)
  42.         {
  43.         if ((*cmpfn)(p_lo, p_i) > 0)
  44.             {
  45.             p_lastlo += elt_size;
  46.             swapfn(p_lastlo, p_i, elt_size);
  47.             }
  48.         }
  49.     swapfn(p_lo, p_lastlo, elt_size);
  50.     iqsort(p_lo, p_lastlo - elt_size, elt_size, cmpfn);
  51.     iqsort(p_lastlo + elt_size, p_hi, elt_size, cmpfn);
  52.     }                                                                                                                                          /*
  53. .PE
  54. .PS 9
  55. /* qsort - the callable entry point */
  56. void qsort(a, n, size, pf)
  57.     data_ptr a;        /* address of array A to be sorted */
  58.     size_t n;        /* number of elements in A */
  59.     size_t size;    /* size of each element */
  60.     int (*pf)();    /* comparison function ptr */
  61.     {
  62.     iqsort((data_ptr)a, (char *)a + (n-1) * size, size, pf);
  63.     }                                                                                                                                          /*
  64. .PE
  65. .PS 14
  66. /* qsortm - test the qsort function */
  67. static int a[100] = 
  68.     {
  69.      0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
  70.     10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
  71.     20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
  72.     30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
  73.     40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
  74.     50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
  75.     60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
  76.     70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
  77.     80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
  78.     90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
  79.     };                                                                                                                                          /*
  80. .PE
  81. .PS 11
  82. /* intcmp - compare two ints */
  83. int intcmp(pi, pj)
  84.     register int *pi, *pj;
  85.     {
  86.     if (*pi < *pj)
  87.         return (-1);
  88.     else if (*pi == *pj)
  89.         return (0);
  90.     else
  91.         return (1);
  92.     }                                                                                                                                          /*
  93. .PE
  94. .PS 10
  95. /* qsortm (main) - run the test */
  96. main(ac, av)
  97.     int ac;
  98.     char *av[];
  99.     {
  100.     int i;
  101.  
  102.     for (i = 1; i <= 1000; ++i)
  103.         qsort((data_ptr)a, 100, sizeof(int), intcmp);
  104.     }
  105.