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