#define DEBUG /* 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