1 /*- 2 * Copyright (c) 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)heapsort.c 5.2 (Berkeley) 07/22/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/cdefs.h> 16 #include <sys/types.h> 17 #include <errno.h> 18 #include <stdlib.h> 19 20 /* 21 * Swap two areas of size number of bytes. Although qsort(3) permits random 22 * blocks of memory to be sorted, sorting pointers is almost certainly the 23 * common case (and, were it not, could easily be made so). Regardless, it 24 * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer 25 * arithmetic gets lost in the time required for comparison function calls. 26 */ 27 #define SWAP(a, b) { \ 28 cnt = size; \ 29 do { \ 30 ch = *a; \ 31 *a++ = *b; \ 32 *b++ = ch; \ 33 } while (--cnt); \ 34 } 35 36 /* 37 * Build the list into a heap, where a heap is defined such that for 38 * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N. 39 * 40 * There two cases. If j == nmemb, select largest of Ki and Kj. If 41 * j < nmemb, select largest of Ki, Kj and Kj+1. 42 * 43 * The initial value depends on if we're building the initial heap or 44 * reconstructing it after saving a value. 45 */ 46 #define HEAP(initval) { \ 47 for (i = initval; (j = i * 2) <= nmemb; i = j) { \ 48 p = (char *)bot + j * size; \ 49 if (j < nmemb && compar(p, p + size) < 0) { \ 50 p += size; \ 51 ++j; \ 52 } \ 53 t = (char *)bot + i * size; \ 54 if (compar(p, t) <= 0) \ 55 break; \ 56 SWAP(t, p); \ 57 } \ 58 } 59 60 /* 61 * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average 62 * and worst. While heapsort is faster than the worst case of quicksort, 63 * the BSD quicksort does median selection so that the chance of finding 64 * a data set that will trigger the worst case is nonexistent. Heapsort's 65 * only advantage over quicksort is that it requires no additional memory. 66 */ 67 heapsort(bot, nmemb, size, compar) 68 register void *bot; 69 register size_t nmemb, size; 70 int (*compar) __P((const void *, const void *)); 71 { 72 register char *p, *t, ch; 73 register int cnt, i, j, l; 74 75 if (nmemb <= 1) 76 return (0); 77 if (!size) { 78 errno = EINVAL; 79 return (-1); 80 } 81 /* 82 * Items are numbered from 1 to nmemb, so offset from size bytes 83 * below the starting address. 84 */ 85 bot -= size; 86 87 for (l = nmemb / 2 + 1; --l;) 88 HEAP(l); 89 90 /* 91 * For each element of the heap, save the largest element into its 92 * final slot, then recreate the heap. 93 */ 94 while (nmemb > 1) { 95 p = (char *)bot + size; 96 t = (char *)bot + nmemb * size; 97 SWAP(p, t); 98 --nmemb; 99 HEAP(1); 100 } 101 return (0); 102 } 103