Output of file : HSORT.C contained in archive : LAPLACE.ZIP
/* hsort - general purpose heapsort

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

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,
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

### 3 Responses to “Category : Science and EducationArchive   : LAPLACE.ZIPFilename : HSORT.C”

1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/