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