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);
}


You are viewing proxied material from gopher.altexxanet.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.