All rights reserved.
This program may be copied for personal, non-profit use only.
Based on algorithms by Jon Bentley [Communications of the ACM v
28 n 3 p 245 (Mar 85) and v 28 n 5 p 456 (May 85)], and the
sort interface routines by Allen I. Holub [Dr. Dobb's Journal
#102 (Apr 85)].
Usage...
Including a #define for DEBUG will make this file a stand-alone
program which sorts argv and prints the result, along with the
heap at the intermediate stages. This is instructive if you
want to see how the heap sort works. #defining DEBUG2 will
also print results of comparisons.
Notes...
This routine sorts N objects in worst-case time proportional to
N*log(N). The heapsort was discovered by J. W. J. Williams
[Communications of the ACM v 7 p 347-348 (1964)] and is
discussed by D. E. Knuth [The Art of Computer Programming,
Volume 3: Sorting and Searching, Addison-Wesley, Reading,
Mass., 1973, section 5.2.3].
This algorithm depends on a portion of an array having the
"heap" property. The array X has the property heap[L,U] if:
for all L, i, and U
such that 2L <= i <= U
we have X[i div 2] <= X[i]
sift_down enlarges the heap: It accepts an array with heap[L+1,U]
and returns an array with heap[L,U].
*/
typedef int (*PFI)(); /* pointer to a function returning int */
static PFI Comp; /* pointer to comparison routine */
static int Width; /* width of an object in bytes */
static char *Base; /* pointer to element [-1] of array */
static char *a, *b, tmp; /* temporaries for exchanges */
#ifdef DEBUG
int Exchanges=0, Comparisons=0;
#endif
/*--------------------------------------------------------------------------*/
int argvcmp(s1p,s2p) char **s1p,**s2p;
{
/* Comparison routine for sorting an argv like list of pointers to
strings. Just remove one level of indirection and call strcmp
to do the comparison */
hsort(base,nel,width,compare)
char *base;
int nel,width;
int (*compare)();
{
static int i,j,n,stop;
/* Perform a heap sort on an array starting at base. The array is
nel elements large and width is the size of a single element in
bytes. Compare is a pointer to a comparison routine which will
be passed pointers to two elements of the array. It should
return a negative number if the left-most argument is less than
the rightmost, 0 if the two arguments are equal, a positive
number if the left argument is greater than the right. (That
is, it acts like a "subtract" operator.) If compare is 0 then
the default comparison routine, argvcmp (which sorts an
argv-like array of pointers to strings), is used. */
#ifdef DEBUG
static int ii;
printf("Sorting %d element array of %d byte elements at 0x%x\n",
nel,width,base);
printf("Comparison routine at 0x%x. Unsorted list:\n",compare);
ptext(1,nel,base);
for ( ii=1 ; ii<=nel ; ii++ ) printf("[%d] ",ii);
printf("\n");
#endif
Width=width;
Comp=(compare==(PFI)0) ? &argvcmp : compare ;
n=nel*Width;
Base=base-Width;
for (i=(n/Width/2)*Width; i>=Width; i-=Width) sift_down(i,n);
#ifdef DEBUG
printf("Heap constructed\n");
for ( ii=1 ; ii<=nel ; ii++ ) printf("[%d] ",ii);
printf("\n");
#endif
stop=Width+Width;
for (i=n; i>=stop; )
{for (b=base, a=Base+i, j=Width ; j-- ; )
{tmp = *b; *b++ = *a; *a++ = tmp;
}
#ifdef DEBUG
Exchanges++;
#endif
sift_down(Width,i-=Width);
}
#ifdef DEBUG
printf("\nSort complete, list is:\n");
ptext(1,nel,base);
printf("%d comparisons and %d exchanges were performed \n",
Comparisons,Exchanges);
#endif
}
/*---------------------------------------------------------------------------*/
static sift_down(L,U) int L,U;
/* pre: heap(L+1,U) */
{ int c,count;
