home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / ddjmag / ddj8908.arc / RUSSELL.LST < prev    next >
File List  |  1989-07-06  |  7KB  |  364 lines
  1. A GENERIC HEAPSORT ALGORITHM IN C
  2. by Stephen Russell
  3.  
  4. [LISTING ONE]
  5.  
  6. /*
  7.  *  The Heapsort to sort an array of n integers.
  8.  */
  9.  
  10. static
  11. fixheap(h, i, n)
  12. int *h;
  13. unsigned i, n;
  14. {
  15.     unsigned k;
  16.     int     tmp;
  17.  
  18.     while ((k = 2 * i) <= n)        /* h[k] = left child of h[i] */
  19.     {
  20.         /*  Find maximum of left and right children */
  21.  
  22.         if (k != n && h[k+1] > h[k])
  23.             ++k;            /* right child is greater */
  24.  
  25.         /* Compare greater of children to parent */
  26.  
  27.         if (h[i] >= h[k])
  28.             return;
  29.  
  30.         /* Parent is less than child, so swap */
  31.  
  32.         tmp = h[k]; h[k] = h[i]; h[i] = tmp;
  33.  
  34.         i = k;                /* move down tree */
  35.     }
  36. }
  37.  
  38.  
  39. hsort(h, n)
  40. int *h;
  41. unsigned n;
  42. {
  43.     unsigned i;
  44.     int     tmp;
  45.  
  46.     --h;            /* adjust for zero-origin arrays in C */
  47.  
  48.     for (i = n/2; i > 1; --i)
  49.         fixheap(h, i, n);    /* build heap, except for h[1] */
  50.  
  51.     while (n > 1)
  52.     {
  53.         fixheap(h, 1, n);    /* move max to h[1] */
  54.         tmp = h[1];        /* move max to final position */
  55.         h[1] = h[n];
  56.         h[n] = tmp;
  57.         --n;            /* reduce size of heap */
  58.     }
  59. }
  60.  
  61. [LISTING TWO]
  62.  
  63.  
  64. /*
  65.  *    Generic Heapsort, derived from listing 1.
  66.  */
  67.  
  68.  
  69. #define    H(k)    (h + k * size)
  70.  
  71. static
  72. swap(p1, p2, n)            /* swap n bytes */
  73. char *p1, *p2;
  74. unsigned n;
  75. {
  76.     char    tmp;
  77.  
  78.     while (n-- != 0)
  79.     {
  80.         tmp = *p1; *p1++ = *p2; *p2++ = tmp;
  81.     }
  82. }
  83.  
  84. static
  85. fixheap(h, size, cmp, i, n)
  86. char *h;
  87. unsigned size, i, n;
  88. int (*cmp)();
  89. {
  90.     unsigned k;
  91.  
  92.     while ((k = 2 * i) <= n)
  93.     {
  94.         if (k != n && (*cmp)(H(k+1), H(k)) > 0)
  95.             ++k;
  96.  
  97.         if ((*cmp)(H(i), H(k)) >= 0)
  98.             return;
  99.  
  100.         swap(H(i), H(k), size);
  101.         i = k;
  102.     }
  103. }
  104.  
  105. hsort(h, n, size, cmp)
  106. char *h;
  107. unsigned n, size;
  108. int (*cmp)();
  109. {
  110.     unsigned i;
  111.  
  112.     h -= size;
  113.  
  114.     for (i = n/2; i > 1; --i)
  115.         fixheap(h, size, cmp, i, n);
  116.  
  117.     while (n > 1)
  118.     {
  119.         fixheap(h, size, cmp, 1, n);
  120.         swap(H(1), H(n), size);
  121.         --n;
  122.     }
  123. }
  124.  
  125.  
  126. [LISTING THREE]
  127.  
  128. /*
  129.  *  Generic Heapsort.
  130.  *
  131.  *  Synopsis:
  132.  *    hsort(char *base, unsigned n, unsigned size, int (*fn)())
  133.  *  Description:
  134.  *    Hsort sorts the array of `n' items which starts at address `base'.
  135.  *    The size of each item is as given.  Items are compared by the function
  136.  *    `fn', which is passed pointers to two items as arguments. The function
  137.  *    should return < 0 if item1 < item2, == 0 if item1 == item2, and > 0
  138.  *    if item1 > item2.
  139.  *  Version:
  140.  *    1988 April 28
  141.  *  Author:
  142.  *    Stephen Russell, Department of Computer Science,
  143.  *    University of Sydney, 2006
  144.  *    Australia.
  145.  */
  146.  
  147. #ifdef INLINE
  148.  
  149. #define    swap(p1, p2, n)    {\
  150.     register char *_p1, *_p2;\
  151.     register unsigned _n;\
  152.     register char _tmp;\
  153. \
  154.     for (_p1 = p1, _p2 = p2, _n = n; _n-- > 0; )\
  155.     {\
  156.         _tmp = *_p1; *_p1++ = *_p2; *_p2++ = _tmp;\
  157.     }\
  158. }\
  159.  
  160. #else
  161.  
  162. /*
  163.  *   Support routine for swapping elements of the array.
  164.  */
  165.  
  166. static
  167. swap(p1, p2, n)
  168. register char     *p1, *p2;
  169. register unsigned n;
  170. {
  171.     register char    ctmp;
  172.  
  173.     /*
  174.      *  On machines with no alignment restrictions for int's,
  175.      *  the following loop may improve performance if moving lots
  176.      *  of data. It has been commented out for portability.
  177.  
  178.      register int    itmp;
  179.  
  180.      for ( ; n > sizeof(int); n -= sizeof(int))
  181.      {
  182.         itmp = *(int *)p1;
  183.         *(int *)p1 = *(int *)p2;
  184.         p1 += sizeof(int);
  185.         *(int *)p2 = itmp;
  186.         p2 += sizeof(int);
  187.     }
  188.  
  189.     */
  190.  
  191.     while (n-- != 0)
  192.     {
  193.         ctmp = *p1; *p1++ = *p2; *p2++ = ctmp;
  194.     }
  195. }
  196.  
  197. #endif
  198.  
  199. /*
  200.  *    To avoid function calls in the inner loops, the code responsible for
  201.  *    constructing a heap from (part of) the array has been expanded inline.
  202.  *    It is possible to convert this common code to a function. The three
  203.  *    parameters base0, cmp and size are invariant - only the size of the
  204.  *    gap and the high bound of the array change. In phase 1, gap decreases
  205.  *    while hi is fixed. In phase 2, gap == size, and hi decreases. The
  206.  *    variables p, q, and g are only used in this common code.
  207.  */
  208.  
  209. hsort(base, n, size, cmp)
  210. char *base;
  211. unsigned n;
  212. unsigned size;
  213. int (*cmp)();
  214. {
  215.     register char     *p, *q, *base0, *hi;
  216.     register unsigned gap, g;
  217.  
  218.     if (n < 2)
  219.         return;
  220.  
  221.     base0 = base - size;        /* set up address of h[0] */
  222.  
  223.     /*
  224.      *  The gap is the distance, in bytes, between h[0] and h[i],
  225.      *  for some i. It is also the distance between h[i] and h[2*i];
  226.      *  that is, the distance between a node and its left child.
  227.      *  The initial node of interest is h[n/2] (the rightmost
  228.      *  interior node), so gap is set accordingly. The following is
  229.      *  the only multiplication needed.
  230.      */
  231.  
  232.     gap = (n >> 1) * size;         /* initial gap is n/2*size */
  233.     hi = base0 + gap + gap;     /* calculate address of h[n] */
  234.     if (n & 1)
  235.         hi += size;        /* watch out for odd arrays */
  236.  
  237.     /*
  238.      *  Phase 1: Construct heap from random data.
  239.      *
  240.      *  For i = n/2 downto 2, ensure h[i] is greater than its
  241.      *  children h[2*i] and h[2*i+1]. By decreasing 'gap' at each
  242.      *  iteration, we move down the heap towards h[2]. The final step
  243.      *  of making h[1] the maximum value is done in the next phase.
  244.      */
  245.  
  246.     for ( ; gap != size; gap -= size)
  247.     {
  248.         /*  fixheap(base0, size, cmp, gap, hi) */
  249.  
  250.         for (p = base0 + (g = gap); (q = p + g) <= hi; p = q)
  251.         {
  252.             g += g;        /* double gap for next level */
  253.  
  254.             /*
  255.              *  Find greater of left and right children.
  256.              */
  257.  
  258.             if (q != hi && (*cmp)(q + size, q) > 0)
  259.             {
  260.                 q += size;    /* choose right child */
  261.                 g += size;    /* follow right subtree */
  262.             }
  263.  
  264.             /*
  265.              *  Compare with parent.
  266.              */
  267.  
  268.             if ((*cmp)(p, q) >= 0)
  269.                 break;        /* order is correct */
  270.     
  271.             swap(p, q, size);    /* swap parent and child */
  272.         }
  273.     }
  274.  
  275.     /*
  276.      *  Phase 2: Each iteration makes the first item in the
  277.      *  array the maximum, then swaps it with the last item, which
  278.      *  is its correct position. The size of the heap is decreased
  279.      *  each iteration. The gap is always "size", as we are interested
  280.      *  in the heap starting at h[1].
  281.      */
  282.  
  283.     for ( ; hi != base; hi -= size)
  284.     {
  285.         /* fixheap(base0, size, cmp, gap (== size), hi) */
  286.  
  287.         p = base;        /* == base0 + size */
  288.         for (g = size; (q = p + g) <= hi; p = q)
  289.         {
  290.             g += g;
  291.             if (q != hi && (*cmp)(q + size, q) > 0)
  292.             {
  293.                 q += size;
  294.                 g += size;
  295.             }
  296.  
  297.             if ((*cmp)(p, q) >= 0)
  298.                 break;
  299.     
  300.             swap(p, q, size);
  301.         }
  302.  
  303.         swap(base, hi, size);        /* move largest item to end */
  304.     }
  305. }
  306.  
  307. [LISTING FOUR]
  308.  
  309.  
  310. /*
  311.  *    Use hsort() to sort an array of strings read from input.
  312.  */
  313.  
  314. #include    <stdio.h>
  315.  
  316.  
  317. #define    MAXN    500
  318. #define    MAXSTR    1000
  319.  
  320.  
  321. cmp(p1, p2)
  322. char **p1, **p2;
  323. {
  324.     return strcmp(*p1, *p2);
  325. }
  326.  
  327. static    char    *string[MAXN];
  328. static    char    buf[MAXSTR];
  329.  
  330. extern    char    *gets();
  331. extern    char    *malloc();
  332.  
  333.  
  334. main()
  335. {
  336.     char    *p;
  337.     int    i, n;
  338.  
  339.     for (n = 0; gets(buf); ++n)
  340.     {
  341.         if (n == MAXN)
  342.         {
  343.             fprintf(stderr, "Too many strings\n");
  344.             exit(1);
  345.         }
  346.  
  347.         p = malloc(strlen(buf) + 1);
  348.         if (p == (char *)NULL)
  349.         {
  350.             fprintf(stderr, "Out of memory\n");
  351.             exit(2);
  352.         }
  353.  
  354.         strcpy(string[n] = p, buf);
  355.     }
  356.  
  357.     hsort(string, n, sizeof string[0], cmp);
  358.  
  359.     for (i = 0; i < n; ++i)
  360.         puts(string[i]);
  361.  
  362.     exit(0);
  363. }
  364.