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.5 (Berkeley) 09/23/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <errno.h> 17 #include <stdlib.h> 18 #include <stddef.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 /* Copy one block of size size to another. */ 37 #define COPY(a, b) { \ 38 cnt = size; \ 39 t1 = a; \ 40 t2 = b; \ 41 do { \ 42 *t1++ = *t2++; \ 43 } while (--cnt); \ 44 } 45 46 /* 47 * Build the list into a heap, where a heap is defined such that for 48 * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N. 49 * 50 * There two cases. If j == nmemb, select largest of Ki and Kj. If 51 * j < nmemb, select largest of Ki, Kj and Kj+1. 52 */ 53 #define CREATE(initval) { \ 54 for (i = initval; (j = i * 2) <= nmemb; i = j) { \ 55 p = (char *)bot + j * size; \ 56 if (j < nmemb && compar(p, p + size) < 0) { \ 57 p += size; \ 58 ++j; \ 59 } \ 60 t = (char *)bot + i * size; \ 61 if (compar(p, t) <= 0) \ 62 break; \ 63 SWAP(t, p); \ 64 } \ 65 } 66 67 /* 68 * Select the top of the heap and 'heapify'. Since by far the most expensive 69 * action is the call to the compar function, a considerable optimization 70 * in the average case can be achieved due to the fact that k, the displaced 71 * elememt, is ususally quite small, so it would be preferable to first 72 * heapify, always maintaining the invariant that the larger child is copied 73 * over its parent's record. 74 * 75 * Then, starting from the *bottom* of the heap, finding k's correct place, 76 * again maintianing the invariant. As a result of the invariant no element 77 * is 'lost' when k is assigned its correct place in the heap. 78 * 79 * The time savings from this optimization are on the order of 15-20% for the 80 * average case. See Knuth, Vol. 3, page 158, problem 18. 81 */ 82 #define SELECT { \ 83 for (i = 1; (j = i * 2) <= nmemb; i = j) { \ 84 p = (char *)bot + j * size; \ 85 if (j < nmemb && compar(p, p + size) < 0) { \ 86 p += size; \ 87 ++j; \ 88 } \ 89 t = (char *)bot + i * size; \ 90 COPY(t, p); \ 91 } \ 92 for (;;) { \ 93 j = i; \ 94 i = j / 2; \ 95 p = (char *)bot + j * size; \ 96 t = (char *)bot + i * size; \ 97 if (j == 1 || compar(k, t) < 0) { \ 98 COPY(p, k); \ 99 break; \ 100 } \ 101 COPY(p, t); \ 102 } \ 103 } 104 105 /* 106 * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average 107 * and worst. While heapsort is faster than the worst case of quicksort, 108 * the BSD quicksort does median selection so that the chance of finding 109 * a data set that will trigger the worst case is nonexistent. Heapsort's 110 * only advantage over quicksort is that it requires little additional memory. 111 */ 112 int 113 heapsort(bot, nmemb, size, compar) 114 void *bot; 115 size_t nmemb, size; 116 int (*compar) __P((const void *, const void *)); 117 { 118 register int cnt, i, j, l; 119 register char ch, *t1, *t2; 120 char *k, *p, *t; 121 122 if (nmemb <= 1) 123 return (0); 124 125 if (!size) { 126 errno = EINVAL; 127 return (-1); 128 } 129 130 if ((k = malloc(size)) == NULL) 131 return (-1); 132 133 /* 134 * Items are numbered from 1 to nmemb, so offset from size bytes 135 * below the starting address. 136 */ 137 bot -= size; 138 139 for (l = nmemb / 2 + 1; --l;) 140 CREATE(l); 141 142 /* 143 * For each element of the heap, save the largest element into its 144 * final slot, save the displaced element (k), then recreate the 145 * heap. 146 */ 147 while (nmemb > 1) { 148 COPY(k, (char *)bot + nmemb * size); 149 COPY((char *)bot + nmemb * size, (char *)bot + size); 150 --nmemb; 151 SELECT; 152 } 153 free(k); 154 return (0); 155 } 156