home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / stdlib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-22  |  8.6 KB  |  221 lines
  1. /* 
  2.  * qsort.c --
  3.  *
  4.  *    Source code for the library routine "qsort".  Taken
  5.  *    from BSD.
  6.  *
  7.  * Copyright 1988 Regents of the University of California
  8.  * Permission to use, copy, modify, and distribute this
  9.  * software and its documentation for any purpose and without
  10.  * fee is hereby granted, provided that the above copyright
  11.  * notice appear in all copies.  The University of California
  12.  * makes no representations about the suitability of this
  13.  * software for any purpose.  It is provided "as is" without
  14.  * express or implied warranty.
  15.  */
  16.  
  17. #ifndef lint
  18. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/qsort.c,v 1.5 89/03/22 00:47:21 rab Exp $ SPRITE (Berkeley)";
  19. #endif /* not lint */
  20.  
  21. #include <stdlib.h>
  22.  
  23. /*
  24.  * qsort.c:
  25.  * Our own version of the system qsort routine which is faster by an average
  26.  * of 25%, with lows and highs of 10% and 50%.
  27.  * The THRESHold below is the insertion sort threshold, and has been adjusted
  28.  * for records of size 48 bytes.
  29.  * The MTHREShold is where we stop finding a better median.
  30.  */
  31.  
  32. #define         THRESH          4               /* threshold for insertion */
  33. #define         MTHRESH         6               /* threshold for median */
  34.  
  35. static  int             (*qcmp)();              /* the comparison routine */
  36. static  int             qsz;                    /* size of each record */
  37. static  int             thresh;                 /* THRESHold in chars */
  38. static  int             mthresh;                /* MTHRESHold in chars */
  39. static  void            qst();
  40. /*
  41.  * qsort:
  42.  * First, set up some global parameters for qst to share.  Then, quicksort
  43.  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
  44.  * It's not...
  45.  */
  46.  
  47. void
  48. qsort(base, n, size, compar)
  49.         char    *base;
  50.         int     n;
  51.         int     size;
  52.         int     (*compar)();
  53. {
  54.         register char c, *i, *j, *lo, *hi;
  55.         char *min, *max;
  56.  
  57.         if (n <= 1)
  58.                 return;
  59.         qsz = size;
  60.         qcmp = compar;
  61.         thresh = qsz * THRESH;
  62.         mthresh = qsz * MTHRESH;
  63.         max = base + n * qsz;
  64.         if (n >= THRESH) {
  65.                 qst(base, max);
  66.                 hi = base + thresh;
  67.         } else {
  68.                 hi = max;
  69.         }
  70.         /*
  71.          * First put smallest element, which must be in the first THRESH, in
  72.          * the first position as a sentinel.  This is done just by searching
  73.          * the first THRESH elements (or the first n if n < THRESH), finding
  74.          * the min, and swapping it into the first position.
  75.          */
  76.         for (j = lo = base; (lo += qsz) < hi; )
  77.                 if (qcmp(j, lo) > 0)
  78.                         j = lo;
  79.         if (j != base) {
  80.                 /* swap j into place */
  81.                 for (i = base, hi = base + qsz; i < hi; ) {
  82.                         c = *j;
  83.                         *j++ = *i;
  84.                         *i++ = c;
  85.                 }
  86.         }
  87.         /*
  88.          * With our sentinel in place, we now run the following hyper-fast
  89.          * insertion sort.  For each remaining element, min, from [1] to [n-1],
  90.          * set hi to the index of the element AFTER which this one goes.
  91.          * Then, do the standard insertion sort shift on a character at a time
  92.          * basis for each element in the frob.
  93.          */
  94.         for (min = base; (hi = min += qsz) < max; ) {
  95.                 while (qcmp(hi -= qsz, min) > 0)
  96.                         /* void */;
  97.                 if ((hi += qsz) != min) {
  98.                         for (lo = min + qsz; --lo >= min; ) {
  99.                                 c = *lo;
  100.                                 for (i = j = lo; (j -= qsz) >= hi; i = j)
  101.                                         *i = *j;
  102.                                 *i = c;
  103.                         }
  104.                 }
  105.         }
  106. }
  107.  
  108. /*
  109.  * qst:
  110.  * Do a quicksort
  111.  * First, find the median element, and put that one in the first place as the
  112.  * discriminator.  (This "median" is just the median of the first, last and
  113.  * middle elements).  (Using this median instead of the first element is a big
  114.  * win).  Then, the usual partitioning/swapping, followed by moving the
  115.  * discriminator into the right place.  Then, figure out the sizes of the two
  116.  * partions, do the smaller one recursively and the larger one via a repeat of
  117.  * this code.  Stopping when there are less than THRESH elements in a partition
  118.  * and cleaning up with an insertion sort (in our caller) is a huge win.
  119.  * All data swaps are done in-line, which is space-losing but time-saving.
  120.  * (And there are only three places where this is done).
  121.  */
  122.  
  123. static void
  124. qst(base, max)
  125.         char *base, *max;
  126. {
  127.         register char c, *i, *j, *jj;
  128.         register int ii;
  129.         char *mid, *tmp;
  130.         int lo, hi;
  131.  
  132.         /*
  133.          * At the top here, lo is the number of characters of elements in the
  134.          * current partition.  (Which should be max - base).
  135.          * Find the median of the first, last, and middle element and make
  136.          * that the middle element.  Set j to largest of first and middle.
  137.          * If max is larger than that guy, then it's that guy, else compare
  138.          * max with loser of first and take larger.  Things are set up to
  139.          * prefer the middle, then the first in case of ties.
  140.          */
  141.         lo = max - base;                /* number of elements as chars */
  142.         do      {
  143.                 mid = i = base + qsz * ((lo / qsz) >> 1);
  144.                 if (lo >= mthresh) {
  145.                         j = (qcmp((jj = base), i) > 0 ? jj : i);
  146.                         if (qcmp(j, (tmp = max - qsz)) > 0) {
  147.                                 /* switch to first loser */
  148.                                 j = (j == jj ? i : jj);
  149.                                 if (qcmp(j, tmp) < 0)
  150.                                         j = tmp;
  151.                         }
  152.                         if (j != i) {
  153.                                 ii = qsz;
  154.                                 do      {
  155.                                         c = *i;
  156.                                         *i++ = *j;
  157.                                         *j++ = c;
  158.                                 } while (--ii);
  159.                         }
  160.                 }
  161.                 /*
  162.                  * Semi-standard quicksort partitioning/swapping
  163.                  */
  164.                 for (i = base, j = max - qsz; ; ) {
  165.                         while (i < mid && qcmp(i, mid) <= 0)
  166.                                 i += qsz;
  167.                         while (j > mid) {
  168.                                 if (qcmp(mid, j) <= 0) {
  169.                                         j -= qsz;
  170.                                         continue;
  171.                                 }
  172.                                 tmp = i + qsz;  /* value of i after swap */
  173.                                 if (i == mid) {
  174.                                         /* j <-> mid, new mid is j */
  175.                                         mid = jj = j;
  176.                                 } else {
  177.                                         /* i <-> j */
  178.                                         jj = j;
  179.                                         j -= qsz;
  180.                                 }
  181.                                 goto swap;
  182.                         }
  183.                         if (i == mid) {
  184.                                 break;
  185.                         } else {
  186.                                 /* i <-> mid, new mid is i */
  187.                                 jj = mid;
  188.                                 tmp = mid = i;  /* value of i after swap */
  189.                                 j -= qsz;
  190.                         }
  191.                 swap:
  192.                         ii = qsz;
  193.                         do      {
  194.                                 c = *i;
  195.                                 *i++ = *jj;
  196.                                 *jj++ = c;
  197.                         } while (--ii);
  198.                         i = tmp;
  199.                 }
  200.                 /*
  201.                  * Look at sizes of the two partitions, do the smaller
  202.                  * one first by recursion, then do the larger one by
  203.                  * making sure lo is its size, base and max are update
  204.                  * correctly, and branching back.  But only repeat
  205.                  * (recursively or by branching) if the partition is
  206.                  * of at least size THRESH.
  207.                  */
  208.                 i = (j = mid) + qsz;
  209.                 if ((lo = j - base) <= (hi = max - i)) {
  210.                         if (lo >= thresh)
  211.                                 qst(base, j);
  212.                         base = i;
  213.                         lo = hi;
  214.                 } else {
  215.                         if (hi >= thresh)
  216.                                 qst(i, max);
  217.                         max = j;
  218.                 }
  219.         } while (lo >= thresh);
  220. }
  221.