home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 161_01 / qsortitm.c < prev    next >
C/C++ Source or Header  |  1985-08-29  |  4KB  |  175 lines
  1. /* qsort - sort array a (dimension n) using quicksort
  2.  * based on Bentley, CACM April 84
  3.  * Iterative version; avoids recursion, uses little stack
  4.  * Comments use notation A[i], a (fictitious) array of things
  5.  * that are of size elt_size.
  6.  */
  7. #include "local.h"
  8.  
  9. #define STACK_DEPTH (sizeof(size_t) * CHAR_BIT)    /* log2(sizeof(A)) */
  10.  
  11. static size_t elt_size = 0;        /* size of one element */
  12. static int (*cmpfn)() = NULL;    /* the comparison function ptr */
  13. /* swapfn - swap  elt_size bytes  a <--> b (internal routine) 
  14.  */
  15. static void swapfn(a, b)
  16.     register char *a;    /* pointer to one element of A */
  17.     register char *b;    /* pointer to another element of A */
  18.     {
  19.     register size_t i;
  20.     char tmp;
  21.  
  22.     LOOPDN(i, elt_size)
  23.         {
  24.         SWAP(*a, *b, tmp);
  25.         ++a, ++b;
  26.         }
  27.     }
  28. /* sort1 - partition one (sub)array, returning p_lastlo */
  29. static char *sort1(p_lo, p_hi)
  30.     char *p_lo;    /* ptr to low element of (sub)array */
  31.     char *p_hi;    /* ptr to high element of (sub)array */
  32.     {
  33.     char *p_mid;
  34.     register char *p_i;    /* pointer to A[i] */
  35.     register char *p_lastlo;    /* pointer to A[lastlo] */
  36.  
  37.     p_mid = p_lo + ((((p_hi - p_lo) / elt_size) / 2) * elt_size);
  38.     swapfn(p_lo, p_mid);    /* pick the middle element as pivot */
  39.     p_lastlo = p_lo;
  40.     for (p_i = p_lo + elt_size;  p_i <= p_hi; p_i += elt_size)
  41.         {
  42.         if ((*cmpfn)(p_lo, p_i) > 0)
  43.             {
  44.             p_lastlo += elt_size;
  45.             swapfn(p_lastlo, p_i);
  46.             }
  47.         }
  48.     swapfn(p_lo, p_lastlo);
  49.     return (p_lastlo);
  50.     }
  51. /* (new page)
  52. .PE
  53. .PS 45
  54.  */
  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.     static char *histack[STACK_DEPTH] = {0};
  63.     static char *lostack[STACK_DEPTH] = {0};
  64.     int istack;    /* index of next free stack cell */
  65.     char *p_lo;    /* ptr to A[lo] */
  66.     char *p_hi;    /* ptr to A[hi] */
  67.     char *p_lastlo;    /* ptr to A[lastlo] */
  68.     char *p_lo1, *p_hi1;    /* partition 1 */
  69.     char *p_lo2, *p_hi2;    /* partition 2 */
  70.     char *tpc;    /* tmp ptr for swaps */
  71.  
  72.     elt_size = size;
  73.     cmpfn = pf;
  74.     istack = 0;
  75.     p_lo = a;
  76.     p_hi = (char *)a + (n-1) * elt_size;
  77.     /* (new page)
  78. .PE
  79. .PS 45
  80.      */
  81.     /* loop until no non-trivial partitions remain */
  82.     while (istack != 0 || p_lo < p_hi)
  83.         {
  84.         p_lastlo = sort1(p_lo, p_hi);
  85.         p_lo1 = p_lo;
  86.         p_hi1 = p_lastlo - elt_size;
  87.         p_lo2 = p_lastlo + elt_size;
  88.         p_hi2 = p_hi;
  89.         if (p_hi1 - p_lo1 > p_hi2 - p_lo2)
  90.             {
  91.             SWAP(p_lo1, p_lo2, tpc);
  92.             SWAP(p_hi1, p_hi2, tpc);
  93.             }
  94.         /* now [p_lo1,p_hi1] is smaller partition */
  95.         if (p_lo1 >= p_hi1)
  96.             {
  97.             if (p_lo2 < p_hi2)
  98.                 {
  99.                 /* do next iteration on [p_lo2, p_hi2] */
  100.                 p_lo = p_lo2;
  101.                 p_hi = p_hi2;
  102.                 }
  103.             else if (istack > 0)
  104.                 {
  105.                 /* take next iteration from stack */
  106.                 --istack;
  107.                 p_hi = histack[istack];
  108.                 p_lo = lostack[istack];
  109.                 }
  110.             else
  111.                 p_hi = p_lo;    /* done */
  112.             }
  113.         else
  114.             {
  115.             /* push [p_lo2, p_hi2] on stack */
  116.             histack[istack] = p_hi2;
  117.             lostack[istack] = p_lo2;
  118.             ++istack;
  119.             /* take next iteration from [p_lo1, p_hi1] */
  120.             p_lo = p_lo1;
  121.             p_hi = p_hi1;
  122.             }
  123.         }
  124.     }
  125. /* qsortm - test the qsort function
  126.  */
  127. #include "local.h"
  128. #include "cputim.h"
  129. static long n_compares = 0;
  130. static int a[10000] = {0};
  131. /* intcmp - compare two ints */
  132. int intcmp(pi, pj)
  133.     register int *pi, *pj;
  134.     {
  135.     ++n_compares;
  136.     if (*pi < *pj)
  137.         return (-1);
  138.     else if (*pi == *pj)
  139.         return (0);
  140.     else
  141.         return (1);
  142.     }
  143. /* qsortm (main) - run the test */
  144. main(ac, av)
  145.     int ac;
  146.     char *av[];
  147.     {
  148.     int i;
  149.     int lim;
  150.     double nlogn;
  151.     double tim;    /* in usec */
  152.     cputim_t cputim();
  153.  
  154.     lim = atoi(av[1]);
  155.     printf("lim=%d\n", lim);
  156.     for (i = 0; i < lim; ++i)
  157.         a[i] = rand();
  158.     printf("start:\n");
  159.     cputim();
  160.     qsort((data_ptr)a, lim, sizeof(int), intcmp);
  161.     tim = 1e6 * (double)cputim() / CLOCK_TICKS_PER_SECOND;
  162.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  163.     nlogn = lim * log((double)lim) / log(2.);
  164.     printf("n_compares = %ld\n", n_compares);
  165.     printf("cpu time = %.3f (usec) per compare\n", tim / n_compares);
  166.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  167.     printf("N log N = %.3f\n", nlogn);
  168.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  169.     printf("ratio of n_compares to N log N = %.3f\n\n", n_compares / nlogn);
  170.     for (i = 0; i < lim-1; ++i)
  171.         if (a[i] > a[i+1])
  172.             error("bad value", "");
  173.     exit(SUCCEED);
  174.     }
  175.