364 lines
6.8 KiB
Plaintext
364 lines
6.8 KiB
Plaintext
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 <stdio.h>
|
||
|
||
|
||
#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);
|
||
}
|
||
|