home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 3 / CDPDIII.bin / pd / programming / gnuc / stdlib / rcs / heapsort.c,v < prev    next >
Encoding:
Text File  |  1992-07-04  |  4.4 KB  |  152 lines
  1. head    1.1;
  2. access;
  3. symbols
  4.     version39-41:1.1;
  5. locks;
  6. comment    @ * @;
  7.  
  8.  
  9. 1.1
  10. date    92.06.08.17.01.06;    author mwild;    state Exp;
  11. branches;
  12. next    ;
  13.  
  14.  
  15. desc
  16. @initial checkin
  17. @
  18.  
  19.  
  20. 1.1
  21. log
  22. @Initial revision
  23. @
  24. text
  25. @/*-
  26.  * Copyright (c) 1991 The Regents of the University of California.
  27.  * All rights reserved.
  28.  *
  29.  * Redistribution and use in source and binary forms, with or without
  30.  * modification, are permitted provided that the following conditions
  31.  * are met:
  32.  * 1. Redistributions of source code must retain the above copyright
  33.  *    notice, this list of conditions and the following disclaimer.
  34.  * 2. Redistributions in binary form must reproduce the above copyright
  35.  *    notice, this list of conditions and the following disclaimer in the
  36.  *    documentation and/or other materials provided with the distribution.
  37.  * 3. All advertising materials mentioning features or use of this software
  38.  *    must display the following acknowledgement:
  39.  *    This product includes software developed by the University of
  40.  *    California, Berkeley and its contributors.
  41.  * 4. Neither the name of the University nor the names of its contributors
  42.  *    may be used to endorse or promote products derived from this software
  43.  *    without specific prior written permission.
  44.  *
  45.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  46.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  47.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  48.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  49.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  50.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  51.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  52.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  53.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  54.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  55.  * SUCH DAMAGE.
  56.  */
  57.  
  58. #if defined(LIBC_SCCS) && !defined(lint)
  59. static char sccsid[] = "@@(#)heapsort.c    5.1 (Berkeley) 6/4/91";
  60. #endif /* LIBC_SCCS and not lint */
  61.  
  62. #define KERNEL
  63. #include "ixemul.h"
  64.  
  65. #include <sys/cdefs.h>
  66. #include <stdlib.h>
  67.  
  68. /*
  69.  * Swap two areas of size number of bytes.  Although qsort(3) permits random
  70.  * blocks of memory to be sorted, sorting pointers is almost certainly the
  71.  * common case (and, were it not, could easily be made so).  Regardless, it
  72.  * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
  73.  * arithmetic gets lost in the time required for comparison function calls.
  74.  */
  75. #define    SWAP(a, b) { \
  76.     cnt = size; \
  77.     do { \
  78.         ch = *a; \
  79.         *a++ = *b; \
  80.         *b++ = ch; \
  81.     } while (--cnt); \
  82. }
  83.  
  84. /*
  85.  * Build the list into a heap, where a heap is defined such that for
  86.  * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
  87.  *
  88.  * There two cases.  If j == nmemb, select largest of Ki and Kj.  If
  89.  * j < nmemb, select largest of Ki, Kj and Kj+1.
  90.  *
  91.  * The initial value depends on if we're building the initial heap or
  92.  * reconstructing it after saving a value.
  93.  */
  94. #define    HEAP(initval) { \
  95.     for (i = initval; (j = i * 2) <= nmemb; i = j) { \
  96.         p = (char *)bot + j * size; \
  97.         if (j < nmemb && compar(p, p + size) < 0) { \
  98.             p += size; \
  99.             ++j; \
  100.         } \
  101.         t = (char *)bot + i * size; \
  102.         if (compar(p, t) <= 0) \
  103.             break; \
  104.         SWAP(t, p); \
  105.     } \
  106. }
  107.  
  108. /*
  109.  * Heapsort -- Knuth, Vol. 3, page 145.  Runs in O (N lg N), both average
  110.  * and worst.  While heapsort is faster than the worst case of quicksort,
  111.  * the BSD quicksort does median selection so that the chance of finding
  112.  * a data set that will trigger the worst case is nonexistent.  Heapsort's
  113.  * only advantage over quicksort is that it requires no additional memory.
  114.  */
  115. heapsort(bot, nmemb, size, compar)
  116.     register void *bot;
  117.     register size_t nmemb, size;
  118.     int (*compar) __P((const void *, const void *));
  119. {
  120.     register char *p, *t, ch;
  121.     register int cnt, i, j, l;
  122.  
  123.     if (nmemb <= 1)
  124.         return (0);
  125.     if (!size) {
  126.         errno = EINVAL;
  127.         return (-1);
  128.     }
  129.     /*
  130.      * Items are numbered from 1 to nmemb, so offset from size bytes
  131.      * below the starting address.
  132.      */
  133.     bot -= size;
  134.  
  135.     for (l = nmemb / 2 + 1; --l;)
  136.         HEAP(l);
  137.  
  138.     /*
  139.      * For each element of the heap, save the largest element into its
  140.      * final slot, then recreate the heap.
  141.      */
  142.     while (nmemb > 1) {
  143.         p = (char *)bot + size;
  144.         t = (char *)bot + nmemb * size;
  145.         SWAP(p, t);
  146.         --nmemb;
  147.         HEAP(1);
  148.     }
  149.     return (0);
  150. }
  151. @
  152.