Category : Science and Education
Archive   : LAPLACE.ZIP
Filename : HSORT.C

/* hsort - general purpose heapsort

Author...
Copyright (c) 1985 James R. Van Zandt

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 */

#ifdef DEBUG
Comparisons++;
#endif
#ifdef DEBUG2
register int rval;
rval=strcmp(*s1p,*s2p);
printf(" argvcmp(<%s><%s>) = %d\n",*s1p,*s2p,rval);
return (rval);
#else
return (strcmp(*s1p,*s2p));
#endif
}

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;

#ifdef DEBUG
int i1;
i1=L;
#endif
while(1)
{c=L+L;
if(c>U) break;
if( (c+Width <= U) && ((*Comp)(Base+c+Width,Base+c)>0) ) c+= Width;
if ((*Comp)(Base+L,Base+c)>=0) break;
for(b=Base+L,a=Base+c,count=Width; count-- ; )
{tmp=*b; *b++ = *a; *a++ = tmp;
}
#ifdef DEBUG
Exchanges++;
#endif
L=c;
}
#ifdef DEBUG
ptext(i1/2,U/2,Base+Width);
#endif
/* post: heap(L,U) */
}

/*--------------------------------------------------------------------------*/
/* Test routine for hsort, compiled if DEBUG is #defined */

#ifdef DEBUG
static ptext( start, end, argv)
int start,end;
char **argv;
{
/* Print out argv, one element per line */

register int i;
for (i=1; i for ( i=start ; i<=end ; i++ ) printf("%-8s",*argv++);
printf("\n");
}

main(argc,argv) int argc; char **argv;
{
/* Test routine for hsort. Sorts argv (less the first element). */

hsort(++argv,--argc,sizeof(PFI),0);
}

#endif