home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / LIBSRC.ZOO / libsrc / stdlib / heapsort.c < prev    next >
C/C++ Source or Header  |  1992-01-26  |  4KB  |  126 lines
  1. /*-
  2.  * Copyright (c) 1991 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[] = "@(#)heapsort.c    5.1 (Berkeley) 6/4/91";
  36. #endif /* LIBC_SCCS and not lint */
  37.  
  38. #include <sys/cdefs.h>
  39. #include <sys/types.h>
  40. #include <errno.h>
  41. #include <stdlib.h>
  42.  
  43. /*
  44.  * Swap two areas of size number of bytes.  Although qsort(3) permits random
  45.  * blocks of memory to be sorted, sorting pointers is almost certainly the
  46.  * common case (and, were it not, could easily be made so).  Regardless, it
  47.  * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
  48.  * arithmetic gets lost in the time required for comparison function calls.
  49.  */
  50. #define    SWAP(a, b) { \
  51.     cnt = size; \
  52.     do { \
  53.         ch = *a; \
  54.         *a++ = *b; \
  55.         *b++ = ch; \
  56.     } while (--cnt); \
  57. }
  58.  
  59. /*
  60.  * Build the list into a heap, where a heap is defined such that for
  61.  * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
  62.  *
  63.  * There two cases.  If j == nmemb, select largest of Ki and Kj.  If
  64.  * j < nmemb, select largest of Ki, Kj and Kj+1.
  65.  *
  66.  * The initial value depends on if we're building the initial heap or
  67.  * reconstructing it after saving a value.
  68.  */
  69. #define    HEAP(initval) { \
  70.     for (i = initval; (j = i * 2) <= nmemb; i = j) { \
  71.         p = (char *)bot + j * size; \
  72.         if (j < nmemb && compar(p, p + size) < 0) { \
  73.             p += size; \
  74.             ++j; \
  75.         } \
  76.         t = (char *)bot + i * size; \
  77.         if (compar(p, t) <= 0) \
  78.             break; \
  79.         SWAP(t, p); \
  80.     } \
  81. }
  82.  
  83. /*
  84.  * Heapsort -- Knuth, Vol. 3, page 145.  Runs in O (N lg N), both average
  85.  * and worst.  While heapsort is faster than the worst case of quicksort,
  86.  * the BSD quicksort does median selection so that the chance of finding
  87.  * a data set that will trigger the worst case is nonexistent.  Heapsort's
  88.  * only advantage over quicksort is that it requires no additional memory.
  89.  */
  90. heapsort(bot, nmemb, size, compar)
  91.     register void *bot;
  92.     register size_t nmemb, size;
  93.     int (*compar) __P((const void *, const void *));
  94. {
  95.     register char *p, *t, ch;
  96.     register int cnt, i, j, l;
  97.  
  98.     if (nmemb <= 1)
  99.         return (0);
  100.     if (!size) {
  101.         errno = EINVAL;
  102.         return (-1);
  103.     }
  104.     /*
  105.      * Items are numbered from 1 to nmemb, so offset from size bytes
  106.      * below the starting address.
  107.      */
  108.     bot -= size;
  109.  
  110.     for (l = nmemb / 2 + 1; --l;)
  111.         HEAP(l);
  112.  
  113.     /*
  114.      * For each element of the heap, save the largest element into its
  115.      * final slot, then recreate the heap.
  116.      */
  117.     while (nmemb > 1) {
  118.         p = (char *)bot + size;
  119.         t = (char *)bot + nmemb * size;
  120.         SWAP(p, t);
  121.         --nmemb;
  122.         HEAP(1);
  123.     }
  124.     return (0);
  125. }
  126.