#define DEBUG
/*	qsort - general purpose quicksort 

	Author...
		Copyright (c) 1984  Allen I. Holub

		All rights reserved.
		This program may be copied for personal, non-profit use only.

		Published in 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 all
		intermediate stages.  This is pretty instructive if you want to
		see how the quick sort works.

*/

#ifdef DEBUG

static int	Lev=0;		/* recursion level */
static int	Maxlev=0;	/* maximum recursion level */
int Comparisons=0, Exchanges=0;
#endif

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

/*---------------------------------------------------------------------------*/
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
	register int rval;
	rval=strcmp(*s1p,*s2p);
	printf("level %d: argvcmp(<%s><%s>) = %d\n",Lev,*s1p,*s2p,rval);
	Comparisons++;
	return (rval);
#else
	return (strcmp(*s1p,*s2p));
#endif
}

qsort(base,nel,width,compare)
char *base;
int	nel,width;
int	(*compare)();
{
	/*	Perform a quick 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
	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(nel,base);
#endif
	Width=width;
	Comp=(compare==(PFI)0) ? &argvcmp : compare ;
	if(nel>1)
		rqsort(base,base+((nel-1)*width));
#ifdef DEBUG
	printf("\nSort complete, list is:\n");
	ptext(nel,base);
	printf("Maximum recursion level = %d\n",Maxlev);
	printf("%d comparisons and %d exchanges were performed \n",
	Comparisons, Exchanges);
#endif
}

/*---------------------------------------------------------------------------*/
static rqsort(low,high)
register char *low,*high;
{
	/*	Workhorse function called by the access routine, qsort().
		Not externally accessible.										*/

	char *pivot,*base;
	static char *a,*b;	/*	Used for exchanges, will not need to retain	*/
	static int tmp,i;	/*	their values during the recursion so they	*/
						/*	can be static								*/
	
#ifdef DEBUG
	printf("New pass, recursion level %d\n",Lev);
	if (Lev>Maxlev) Maxlev=Lev;
#endif
	base=low;		/* remember base address of array	*/
	pivot=high;		/* partition off the pivot			*/
	high -= Width;

	do
		{while( low<high && (*Comp)(low,pivot) <= 0)  low += Width;
		while( low<high && (*Comp)(high,pivot) >= 0 ) high -= Width;
		if( low < high )	/* exchange low & high */
			{
#ifdef DEBUG
			printf("lev %d: exchanging high: <%s> & low: <%s>\n",
				Lev,*((char **)high), *((char **)low));
#endif
			for ( b=low,a=high,i=Width ; --i>=0 ; )
				{tmp = *b;	/* Exchange *low and *high */
				*b++ = *a;
				*a++ = tmp;
#ifdef DEBUG
	Exchanges++;
#endif
				}
			}
		} while ( low<high );
#ifdef DEBUG
		printf("level %d: Exchanging pivot:<%s>  & low:<%s>\n",
			Lev, *((char **)pivot), *((char**)low) );
#endif
		if( low < pivot && (*Comp)(low, pivot) > 0 )
			for ( b=low,a=pivot,i=Width ; --i >=0 ; )
				{tmp=*b ;	/* Exchange *low and *pivot */
				*b++=*a;
				*a++=tmp;
#ifdef DEBUG
	Exchanges++;
#endif
				}
#ifdef DEBUG
		printf("\nDone with pass, partially sorted list =\n");
		ptext( ((pivot - base)/Width) + 1,base );
		printf("\n");
		++Lev;
#endif
		low += Width;
		if( high-base < pivot-low )
			{if( low < pivot ) rqsort( low , pivot );
			if(base < high ) rqsort( base , high );
			}
		else
			{if( base < high ) rqsort( base , high );
			if( low < pivot ) rqsort( low , pivot );
			}
#ifdef DEBUG
		--Lev;
#endif
}
		
/*---------------------------------------------------------------------------*/
/*		Test routine for qsort, compiled if DEBUG is #defined				*/

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

	register int i;
	for ( i=1 ; --argc>=0 ; i++ ) printf("%2d: %s\n",i,*argv++);
}

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

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

#endif