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