A GENERIC HEAPSORT ALGORITHM IN C by Stephen Russell [LISTING ONE] /* * The Heapsort to sort an array of n integers. */ static fixheap(h, i, n) int *h; unsigned i, n; { unsigned k; int tmp; while ((k = 2 * i) <= n) /* h[k] = left child of h[i] */ { /* Find maximum of left and right children */ if (k != n && h[k+1] > h[k]) ++k; /* right child is greater */ /* Compare greater of children to parent */ if (h[i] >= h[k]) return; /* Parent is less than child, so swap */ tmp = h[k]; h[k] = h[i]; h[i] = tmp; i = k; /* move down tree */ } } hsort(h, n) int *h; unsigned n; { unsigned i; int tmp; --h; /* adjust for zero-origin arrays in C */ for (i = n/2; i > 1; --i) fixheap(h, i, n); /* build heap, except for h[1] */ while (n > 1) { fixheap(h, 1, n); /* move max to h[1] */ tmp = h[1]; /* move max to final position */ h[1] = h[n]; h[n] = tmp; --n; /* reduce size of heap */ } } [LISTING TWO] /* * Generic Heapsort, derived from listing 1. */ #define H(k) (h + k * size) static swap(p1, p2, n) /* swap n bytes */ char *p1, *p2; unsigned n; { char tmp; while (n-- != 0) { tmp = *p1; *p1++ = *p2; *p2++ = tmp; } } static fixheap(h, size, cmp, i, n) char *h; unsigned size, i, n; int (*cmp)(); { unsigned k; while ((k = 2 * i) <= n) { if (k != n && (*cmp)(H(k+1), H(k)) > 0) ++k; if ((*cmp)(H(i), H(k)) >= 0) return; swap(H(i), H(k), size); i = k; } } hsort(h, n, size, cmp) char *h; unsigned n, size; int (*cmp)(); { unsigned i; h -= size; for (i = n/2; i > 1; --i) fixheap(h, size, cmp, i, n); while (n > 1) { fixheap(h, size, cmp, 1, n); swap(H(1), H(n), size); --n; } } [LISTING THREE] /* * Generic Heapsort. * * Synopsis: * hsort(char *base, unsigned n, unsigned size, int (*fn)()) * Description: * Hsort sorts the array of `n' items which starts at address `base'. * The size of each item is as given. Items are compared by the function * `fn', which is passed pointers to two items as arguments. The function * should return < 0 if item1 < item2, == 0 if item1 == item2, and > 0 * if item1 > item2. * Version: * 1988 April 28 * Author: * Stephen Russell, Department of Computer Science, * University of Sydney, 2006 * Australia. */ #ifdef INLINE #define swap(p1, p2, n) {\ register char *_p1, *_p2;\ register unsigned _n;\ register char _tmp;\ \ for (_p1 = p1, _p2 = p2, _n = n; _n-- > 0; )\ {\ _tmp = *_p1; *_p1++ = *_p2; *_p2++ = _tmp;\ }\ }\ #else /* * Support routine for swapping elements of the array. */ static swap(p1, p2, n) register char *p1, *p2; register unsigned n; { register char ctmp; /* * On machines with no alignment restrictions for int's, * the following loop may improve performance if moving lots * of data. It has been commented out for portability. register int itmp; for ( ; n > sizeof(int); n -= sizeof(int)) { itmp = *(int *)p1; *(int *)p1 = *(int *)p2; p1 += sizeof(int); *(int *)p2 = itmp; p2 += sizeof(int); } */ while (n-- != 0) { ctmp = *p1; *p1++ = *p2; *p2++ = ctmp; } } #endif /* * To avoid function calls in the inner loops, the code responsible for * constructing a heap from (part of) the array has been expanded inline. * It is possible to convert this common code to a function. The three * parameters base0, cmp and size are invariant - only the size of the * gap and the high bound of the array change. In phase 1, gap decreases * while hi is fixed. In phase 2, gap == size, and hi decreases. The * variables p, q, and g are only used in this common code. */ hsort(base, n, size, cmp) char *base; unsigned n; unsigned size; int (*cmp)(); { register char *p, *q, *base0, *hi; register unsigned gap, g; if (n < 2) return; base0 = base - size; /* set up address of h[0] */ /* * The gap is the distance, in bytes, between h[0] and h[i], * for some i. It is also the distance between h[i] and h[2*i]; * that is, the distance between a node and its left child. * The initial node of interest is h[n/2] (the rightmost * interior node), so gap is set accordingly. The following is * the only multiplication needed. */ gap = (n >> 1) * size; /* initial gap is n/2*size */ hi = base0 + gap + gap; /* calculate address of h[n] */ if (n & 1) hi += size; /* watch out for odd arrays */ /* * Phase 1: Construct heap from random data. * * For i = n/2 downto 2, ensure h[i] is greater than its * children h[2*i] and h[2*i+1]. By decreasing 'gap' at each * iteration, we move down the heap towards h[2]. The final step * of making h[1] the maximum value is done in the next phase. */ for ( ; gap != size; gap -= size) { /* fixheap(base0, size, cmp, gap, hi) */ for (p = base0 + (g = gap); (q = p + g) <= hi; p = q) { g += g; /* double gap for next level */ /* * Find greater of left and right children. */ if (q != hi && (*cmp)(q + size, q) > 0) { q += size; /* choose right child */ g += size; /* follow right subtree */ } /* * Compare with parent. */ if ((*cmp)(p, q) >= 0) break; /* order is correct */ swap(p, q, size); /* swap parent and child */ } } /* * Phase 2: Each iteration makes the first item in the * array the maximum, then swaps it with the last item, which * is its correct position. The size of the heap is decreased * each iteration. The gap is always "size", as we are interested * in the heap starting at h[1]. */ for ( ; hi != base; hi -= size) { /* fixheap(base0, size, cmp, gap (== size), hi) */ p = base; /* == base0 + size */ for (g = size; (q = p + g) <= hi; p = q) { g += g; if (q != hi && (*cmp)(q + size, q) > 0) { q += size; g += size; } if ((*cmp)(p, q) >= 0) break; swap(p, q, size); } swap(base, hi, size); /* move largest item to end */ } } [LISTING FOUR] /* * Use hsort() to sort an array of strings read from input. */ #include #define MAXN 500 #define MAXSTR 1000 cmp(p1, p2) char **p1, **p2; { return strcmp(*p1, *p2); } static char *string[MAXN]; static char buf[MAXSTR]; extern char *gets(); extern char *malloc(); main() { char *p; int i, n; for (n = 0; gets(buf); ++n) { if (n == MAXN) { fprintf(stderr, "Too many strings\n"); exit(1); } p = malloc(strlen(buf) + 1); if (p == (char *)NULL) { fprintf(stderr, "Out of memory\n"); exit(2); } strcpy(string[n] = p, buf); } hsort(string, n, sizeof string[0], cmp); for (i = 0; i < n; ++i) puts(string[i]); exit(0); } 