Enter your search terms Submit search form
	Web pdp-10.trailing-edge.com

/*
**	QSORT	- Sort array
**
**	Author unknown, but believed to be Richard Stallman of the
**	Free Software Foundation, in which case the GNU/FSF license
**	provisions would apply.  --KLH
*/

/*
 * qsort.c:
 * Our own version of the system qsort routine which is faster by an average
 * of 25%, with lows and highs of 10% and 50%.
 * The THRESHold below is the insertion sort threshold, and has been adjusted
 * for records of size 48 bytes.
 * The MTHREShold is where we stop finding a better median.
 */

#include <stdio.h>

#define		THRESH		4		/* threshold for insertion */
#define		MTHRESH		6		/* threshold for median */

static  int		(*qcmp)();		/* the comparison routine */
static  int		qsz;			/* size of each record */

static  int		thresh;			/* THRESHold in chars */
static  int		mthresh;		/* MTHRESHold in chars */
static qst();


/*
 * qsort:
 * First, set up some global parameters for qst to share.  Then, quicksort
 * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
 * It's not...
 */

qsort( base, n, size, compar )

    char		*base;
    int			n;
    int			size;
    int			(*compar)();
{
	register  char		*i, *j, *lo, *hi, *min;
	register  int		c;
	char			*max;

	if(  n  <=  1  )  return;
	qsz = size;
	qcmp = compar;
	thresh = qsz*THRESH;
	mthresh = qsz*MTHRESH;
	max = base + n*qsz;
	if(  n  >=  THRESH  )  {
	    qst( base, max );
	    hi = base + thresh;
	}
	else  {
	    hi = max;
	}
    /*
     * First put smallest element, which must be in the first THRESH, in
     * the first position as a sentinel.  This is done just by searching
     * the first THRESH elements (or the first n if n < THRESH), finding
     * the min, and swapping it into the first position.
     */
	for( j = lo = base; (lo += qsz) < hi; )  {
	    if(  (*qcmp)( j, lo )  >  0  )  j = lo;
	}
	if(  j  !=  base  )  {			/* swap j into place */
	    for( i = base, hi = base + qsz; i < hi; )  {
		c = *j;
		*j++ = *i;
		*i++ = c;
	    }
	}
    /*
     * With our sentinel in place, we now run the following hyper-fast
     * insertion sort.  For each remaining element, min, from [1] to [n-1],
     * set hi to the index of the element AFTER which this one goes.
     * Then, do the standard insertion sort shift on a character at a time
     * basis for each element in the frob.
     */
	for( min = base; (hi = min += qsz) < max; )  {
	    while(  (*qcmp)( hi -= qsz, min )  >  0  );
	    if(  ( hi += qsz )  !=  min  )  {
		for( lo = min + qsz; --lo >= min; )  {
		    c = *lo;
		    for( i = j = lo; (j -= qsz) >= hi; i = j )  *i = *j;
		    *i = c;
		}
	    }
	}
}



/*
 * qst:
 * Do a quicksort
 * First, find the median element, and put that one in the first place as the
 * discriminator.  (This "median" is just the median of the first, last and
 * middle elements).  (Using this median instead of the first element is a big
 * win).  Then, the usual partitioning/swapping, followed by moving the
 * discriminator into the right place.  Then, figure out the sizes of the two
 * partions, do the smaller one recursively and the larger one via a repeat of
 * this code.  Stopping when there are less than THRESH elements in a partition
 * and cleaning up with an insertion sort (in our caller) is a huge win.
 * All data swaps are done in-line, which is space-losing but time-saving.
 * (And there are only three places where this is done).
 */

static  qst( base, max )

    char		*base, *max;
{
	register  char		*i, *j, *jj, *mid;
	register  int		ii, c;
	char			*tmp;
	int			lo, hi;

	lo = max - base;		/* number of elements as chars */
	do  {
    /*
     * At the top here, lo is the number of characters of elements in the
     * current partition.  (Which should be max - base).
     * Find the median of the first, last, and middle element and make that the
     * middle element.  Set j to largest of first and middle.  If max is larger
     * than that guy, then it's that guy, else compare max with loser of first
     * and take larger.  Things are set up to prefer the middle, then the first
     * in case of ties.
     */
	    mid = i = base + qsz*( (unsigned) (lo/qsz) >> 1 );
	    if(  lo  >=  mthresh  )  {
		j = ( (*qcmp)( (jj = base), i ) > 0 ? jj : i );
		if(  (*qcmp)( j, (tmp = max - qsz) )  >  0  )  {
		    j = ( j == jj ? i : jj );	/* switch to first loser */
		    if(  (*qcmp)( j, tmp )  <  0  )  j = tmp;
		}
		if(  j  !=  i  )  {
		    ii = qsz;
		    do  {
			c = *i;
			*i++ = *j;
			*j++ = c;
		    }  while(  --ii  );
		}
	    }
    /*
     * Semi-standard quicksort partitioning/swapping
     */
	    for( i = base, j = max - qsz; ;  )  {
		while(  i < mid  &&  (*qcmp)( i, mid ) <= 0  )  i += qsz;
		while(  j  >  mid  )  {
		    if(  (*qcmp)( mid, j )  <=  0  )  {
			j -= qsz;
			continue;
		    }
		    tmp = i + qsz;		/* value of i after swap */
		    if(  i  ==  mid  )  {	/* j <-> mid, new mid is j */
			mid = jj = j;
		    }
		    else  {			/* i <-> j */
			jj = j;
			j -= qsz;
		    }
		    goto  swap;
		}
		if(  i  ==  mid  )  {
		    break;
		}
		else  {				/* i <-> mid, new mid is i */
		    jj = mid;
		    tmp = mid = i;		/* value of i after swap */
		    j -= qsz;
		}
 swap:
		ii = qsz;
		do  {
		    c = *i;
		    *i++ = *jj;
		    *jj++ = c;
		}  while(  --ii  );
		i = tmp;
	    }
    /*
     * Look at sizes of the two partitions, do the smaller one first by
     * recursion, then do the larger one by making sure lo is its size,
     * base and max are update correctly, and branching back.
     * But only repeat (recursively or by branching) if the partition is
     * of at least size THRESH.
     */
	    i = (j = mid) + qsz;
	    if(  ( lo = j - base )  <=  ( hi = max - i )  )  {
		if(  lo  >=  thresh  )  qst( base, j );
		base = i;
		lo = hi;
	    }
	    else  {
		if(  hi  >=  thresh  )  qst( i, max );
		max = j;
	    }
	}  while(  lo  >=  thresh  );
}