home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / LIBSRC.ZOO / libsrc / stdlib / qsort.c < prev    next >
C/C++ Source or Header  |  1992-01-26  |  8KB  |  276 lines
  1. /*-
  2.  * Copyright (c) 1980, 1983, 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #if defined(LIBC_SCCS) && !defined(lint)
  35. static char sccsid[] = "@(#)qsort.c    5.9 (Berkeley) 2/23/91";
  36. #endif /* LIBC_SCCS and not lint */
  37.  
  38. #include <sys/types.h>
  39. #include <stdlib.h>
  40.  
  41. /*
  42.  * MTHRESH is the smallest partition for which we compare for a median
  43.  * value instead of using the middle value.
  44.  */
  45. #define    MTHRESH    6
  46.  
  47. /*
  48.  * THRESH is the minimum number of entries in a partition for continued
  49.  * partitioning.
  50.  */
  51. #define    THRESH    4
  52.  
  53. void
  54. qsort(bot, nmemb, size, compar)
  55.     void *bot;
  56.     size_t nmemb, size;
  57.     int (*compar) __P((const void *, const void *));
  58. {
  59.     static void insertion_sort(), quick_sort();
  60.  
  61.     if (nmemb <= 1)
  62.         return;
  63.  
  64.     if (nmemb >= THRESH)
  65.         quick_sort(bot, nmemb, size, compar);
  66.     else
  67.         insertion_sort(bot, nmemb, size, compar);
  68. }
  69.  
  70. /*
  71.  * Swap two areas of size number of bytes.  Although qsort(3) permits random
  72.  * blocks of memory to be sorted, sorting pointers is almost certainly the
  73.  * common case (and, were it not, could easily be made so).  Regardless, it
  74.  * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
  75.  * arithmetic gets lost in the time required for comparison function calls.
  76.  */
  77. #define    SWAP(a, b) { \
  78.     cnt = size; \
  79.     do { \
  80.         ch = *a; \
  81.         *a++ = *b; \
  82.         *b++ = ch; \
  83.     } while (--cnt); \
  84. }
  85.  
  86. /*
  87.  * Knuth, Vol. 3, page 116, Algorithm Q, step b, argues that a single pass
  88.  * of straight insertion sort after partitioning is complete is better than
  89.  * sorting each small partition as it is created.  This isn't correct in this
  90.  * implementation because comparisons require at least one (and often two)
  91.  * function calls and are likely to be the dominating expense of the sort.
  92.  * Doing a final insertion sort does more comparisons than are necessary
  93.  * because it compares the "edges" and medians of the partitions which are
  94.  * known to be already sorted.
  95.  *
  96.  * This is also the reasoning behind selecting a small THRESH value (see
  97.  * Knuth, page 122, equation 26), since the quicksort algorithm does less
  98.  * comparisons than the insertion sort.
  99.  */
  100. #define    SORT(bot, n) { \
  101.     if (n > 1) \
  102.         if (n == 2) { \
  103.             t1 = bot + size; \
  104.             if (compar(t1, bot) < 0) \
  105.                 SWAP(t1, bot); \
  106.         } else \
  107.             insertion_sort(bot, n, size, compar); \
  108. }
  109.  
  110. static void
  111. quick_sort(bot, nmemb, size, compar)
  112.     register char *bot;
  113.     register int size;
  114.     int nmemb, (*compar)();
  115. {
  116.     register int cnt;
  117.     register u_char ch;
  118.     register char *top, *mid, *t1, *t2;
  119.     register int n1, n2;
  120.     char *bsv;
  121.     static void insertion_sort();
  122.  
  123.     /* bot and nmemb must already be set. */
  124. partition:
  125.  
  126.     /* find mid and top elements */
  127.     mid = bot + size * (nmemb >> 1);
  128.     top = bot + (nmemb - 1) * size;
  129.  
  130.     /*
  131.      * Find the median of the first, last and middle element (see Knuth,
  132.      * Vol. 3, page 123, Eq. 28).  This test order gets the equalities
  133.      * right.
  134.      */
  135.     if (nmemb >= MTHRESH) {
  136.         n1 = compar(bot, mid);
  137.         n2 = compar(mid, top);
  138.         if (n1 < 0 && n2 > 0)
  139.             t1 = compar(bot, top) < 0 ? top : bot;
  140.         else if (n1 > 0 && n2 < 0)
  141.             t1 = compar(bot, top) > 0 ? top : bot;
  142.         else
  143.             t1 = mid;
  144.  
  145.         /* if mid element not selected, swap selection there */
  146.         if (t1 != mid) {
  147.             SWAP(t1, mid);
  148.             mid -= size;
  149.         }
  150.     }
  151.  
  152.     /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */
  153. #define    didswap    n1
  154. #define    newbot    t1
  155. #define    replace    t2
  156.     didswap = 0;
  157.     for (bsv = bot;;) {
  158.         for (; bot < mid && compar(bot, mid) <= 0; bot += size);
  159.         while (top > mid) {
  160.             if (compar(mid, top) <= 0) {
  161.                 top -= size;
  162.                 continue;
  163.             }
  164.             newbot = bot + size;    /* value of bot after swap */
  165.             if (bot == mid)        /* top <-> mid, mid == top */
  166.                 replace = mid = top;
  167.             else {            /* bot <-> top */
  168.                 replace = top;
  169.                 top -= size;
  170.             }
  171.             goto swap;
  172.         }
  173.         if (bot == mid)
  174.             break;
  175.  
  176.         /* bot <-> mid, mid == bot */
  177.         replace = mid;
  178.         newbot = mid = bot;        /* value of bot after swap */
  179.         top -= size;
  180.  
  181. swap:        SWAP(bot, replace);
  182.         bot = newbot;
  183.         didswap = 1;
  184.     }
  185.  
  186.     /*
  187.      * Quicksort behaves badly in the presence of data which is already
  188.      * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2.
  189.      * To avoid this worst case behavior, if a re-partitioning occurs
  190.      * without swapping any elements, it is not further partitioned and
  191.      * is insert sorted.  This wins big with almost sorted data sets and
  192.      * only loses if the data set is very strangely partitioned.  A fix
  193.      * for those data sets would be to return prematurely if the insertion
  194.      * sort routine is forced to make an excessive number of swaps, and
  195.      * continue the partitioning.
  196.      */
  197.     if (!didswap) {
  198.         insertion_sort(bsv, nmemb, size, compar);
  199.         return;
  200.     }
  201.  
  202.     /*
  203.      * Re-partition or sort as necessary.  Note that the mid element
  204.      * itself is correctly positioned and can be ignored.
  205.      */
  206. #define    nlower    n1
  207. #define    nupper    n2
  208.     bot = bsv;
  209.     nlower = (mid - bot) / size;    /* size of lower partition */
  210.     mid += size;
  211.     nupper = nmemb - nlower - 1;    /* size of upper partition */
  212.  
  213.     /*
  214.      * If must call recursively, do it on the smaller partition; this
  215.      * bounds the stack to lg N entries.
  216.      */
  217.     if (nlower > nupper) {
  218.         if (nupper >= THRESH)
  219.             quick_sort(mid, nupper, size, compar);
  220.         else {
  221.             SORT(mid, nupper);
  222.             if (nlower < THRESH) {
  223.                 SORT(bot, nlower);
  224.                 return;
  225.             }
  226.         }
  227.         nmemb = nlower;
  228.     } else {
  229.         if (nlower >= THRESH)
  230.             quick_sort(bot, nlower, size, compar);
  231.         else {
  232.             SORT(bot, nlower);
  233.             if (nupper < THRESH) {
  234.                 SORT(mid, nupper);
  235.                 return;
  236.             }
  237.         }
  238.         bot = mid;
  239.         nmemb = nupper;
  240.     }
  241.     goto partition;
  242.     /* NOTREACHED */
  243. }
  244.  
  245. static void
  246. insertion_sort(bot, nmemb, size, compar)
  247.     char *bot;
  248.     register int size;
  249.     int nmemb, (*compar)();
  250. {
  251.     register int cnt;
  252.     register u_char ch;
  253.     register char *s1, *s2, *t1, *t2, *top;
  254.  
  255.     /*
  256.      * A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm
  257.      * S).  Insertion sort has the same worst case as most simple sorts
  258.      * (O N^2).  It gets used here because it is (O N) in the case of
  259.      * sorted data.
  260.      */
  261.     top = bot + nmemb * size;
  262.     for (t1 = bot + size; t1 < top;) {
  263.         for (t2 = t1; (t2 -= size) >= bot && compar(t1, t2) < 0;);
  264.         if (t1 != (t2 += size)) {
  265.             /* Bubble bytes up through each element. */
  266.             for (cnt = size; cnt--; ++t1) {
  267.                 ch = *t1;
  268.                 for (s1 = s2 = t1; (s2 -= size) >= t2; s1 = s2)
  269.                     *s1 = *s2;
  270.                 *s1 = ch;
  271.             }
  272.         } else
  273.             t1 += size;
  274.     }
  275. }
  276.