/* Taken from
* http://www.zip.com.au/~raf2/lib/hsort/hsort.c
*/
/*
* Generic Heapsort.
*
* Synopsis:
* hsort(void *base, size_t n, size_t size, int (*fn)(void *, void *))
* 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.
*/
#include
void hsort( void *base, size_t n, size_t size, int (*cmp)(const void *, const void *) );
#ifdef INLINE
#define swap(p1, p2, n) \
{\
register char *_p1, *_p2;\
register size_t _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 void swap
(
register char *p1,
register char *p2,
register size_t 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.
*/
void hsort
(
void *base,
size_t n,
size_t size,
int (*cmp)(const void *, const void *)
)
{
register char *p, *q, *base0, *hi;
register unsigned int gap, g;
if (n < 2)
return;
base0 = (char *)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 = (char *)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((char *)base, hi, size); /* move largest item to end */
}
}
#ifdef TEST
#include
#include
typedef int (*cmpf_t)(const void *, const void *);
#define MAXN 500
#define MAXSTR 1000
static char *string[MAXN];
static char buf[MAXSTR];
int cmp(const char **p1, const char **p2)
{
return strcmp(*p1, *p2);
}
int main(void)
{
char *p;
int i, n;
for (n = 0; n < MAXN && fgets(buf, MAXSTR, stdin); ++n)
{
p = (char *)malloc(strlen(buf) + 1);
if (p == (char *)NULL)
{
fprintf(stderr, "Out of memory\n");
exit(1);
}
strcpy(string[n] = p, buf);
}
hsort(string, n, sizeof string[0], (cmpf_t)cmp);
fputs("\nSorted:\n\n", stdout);
for (i = 0; i < n; ++i)
fputs(string[i], stdout);
exit(0);
return 0;
}
#endif