/*
 * program to do a generic quicksort
 * invocation:
 *	quicksort	prints two arrays of sorted numbers
 * exit code: success, always
 * author: Matt Bishop, bishop@cs.ucdavis.edu, 9/20/96
 */
/*************** THIS PART IS THE DRIVER *********************/
#include <stdio.h>
#include <stdlib.h>

/*
 * forward declaration
 */
void qcksort(void *, int, unsigned, int (*cmp)(void *, void *));

/*
 * the sample arrays to be sorted
 * these are of different types
 */
					/* the integer array */
int arr[] = { 1, 2, 3, 8, 9, 4, 6, 0, 7, 5, };
int szarr = sizeof(arr)/sizeof(int);
					/* the double array */
double darr[] = { 2.34, 6.95, -7.12, 0, 3.68, 5.38, 1.4e2, -1.4e-2, 3.14159, };
int szdarr = sizeof(darr)/sizeof(double);

/*
 * the comparison functions
 */
/* integer */
int intcmp(void *x, void *y)
{
	return(*((int *)x) - *((int *)y));
}
/* double */
int dblcmp(void *x, void *y)
{
	double tmp = *((double *) x) - *((double *)y);
	return((tmp == 0.0) ? 0 : (tmp < 0.0) ? -1 : 1);
}

/*
 * the driver
 */
int main(void)
{
	register int i;		/* counter in a for loop */

	/*
	 * first sort and print the integer array
	 */
	printf("Sorting integer array:");
	qcksort(arr, szarr, sizeof(int), intcmp);
	for(i = 0; i < szarr; i++)
		printf(" %d", arr[i]);
	putchar('\n');

	/*
	 * then sort and print the double array
	 */
	printf("Sorting double array:");
	qcksort(darr, szdarr, sizeof(double), dblcmp);
	for(i = 0; i < szdarr; i++)
		printf(" %f", darr[i]);
	putchar('\n');

	/*
	 * bye!
	 */
	return(EXIT_SUCCESS);
}

/*************** THIS PART IS THE DRIVER *********************/

/*
 * we get passed an address and a size; we need to use the
 * address in pointer arithmetic but can't do it with a void
 * pointer. so BYTE is the type representing one machine
 * address. On most UNIX systems, this is a char.
 */
typedef char BYTE;

/*
 * forward declaration
 */
int partition(void *, int, unsigned, int (*cmp)(void *, void *)); 

/*
 * the quicksort routine
 */
void qcksort(void *a, int nelem, unsigned size, int (*cmp)(void *, void *))
{
	register int pivot;		/* index of midpoint */

	/*
	 * terminal case: if 1 or less elements,
	 * nothing to sort
	 */
	if (nelem <= 1)
		return;

	/*
	 * determine the best pivot
	 * and order the array about it
	 */
	pivot = partition(a, nelem, size, cmp);

	/*
	 * sort the part less than the pivot
	 */
	qcksort(a, nelem - pivot, size, cmp);

	/*
	 * sort the part greater than the pivot
	 */
	qcksort((BYTE *) a + size * pivot, nelem - pivot, size, cmp);
}

/*
 * here's a macro to swap two of these things
 */
#define SWAPV(x, y, sz, tmp, loopvar)				\
		for(loopvar = 0; loopvar < sz; loopvar++){	\
			tmp = (x)[loopvar];			\
			(x)[loopvar] = (y)[loopvar];		\
			(y)[loopvar] = tmp;			\
		}
	
/*
 * now find a pivot p and move elements around so that
 * if x < p then index(x) < index(p), and if x > p
 * then index(x) > index(p)
 */
int partition(void *first, int nelem, unsigned size, int (*cmp)(void *, void *))
{
	BYTE *low, *high;	/* low, high bounds for interval of sort */
	BYTE *piv;		/* the pivot */
	register int i;		/* counter in a for loop */
	BYTE tmp;		/* used to swap element of array */

	/*
	 * pick the pivot as the median of the first, middle,
	 * and last element. Put the median in the middle; that
	 */
	low = (BYTE *) first;
	high = (BYTE *) first + (nelem-1) * size;
	piv = (BYTE *) first + (nelem / 2) * size;
	if (((*cmp)(low, high) > 0 && (*cmp)(high, piv) > 0) ||
			((*cmp)(piv, high) > 0 && (*cmp)(high, low) > 0))
		SWAPV(piv, high, size, tmp, i);
	if (((*cmp)(high, low) > 0 && (*cmp)(low, piv) > 0) ||
			((*cmp)(piv, low) > 0 && (*cmp)(low, high) > 0))
		SWAPV(piv, low, size, tmp, i);
	/*
	 * now swap elements around so that:
	 * x[i] < x[p] ==> i < p
	 * x[i] > x[p] ==> i > p
	 */
	for(; low < high;){
		/* go from high down until you find */
		/* an element less than the pivot   */
		while (low < high && (*cmp)(high, piv) > 0)
			high -= size;
		/* go from low up until you find an */
		/* element greater than the pivot   */
		while (low < high && (*cmp)(low, piv) < 0)
			low += size;
		/* now swap the elements; note that */
		/* if either is the pivot, we keep  */
		/* track of it so we can get the    */
		/* the right index                   */
		if (low < high){
			/* reset pivot if ned be */
			if (low == piv) piv = high;
			else if (high == piv) piv = low;
			/* swap the elements */
			SWAPV(high, low, size, tmp, i);
			/* update the bounds */
			high -= size;
			low += size;
		}
	}

	/*
	 * now return the pivot's index
	 * this is essentially scaling, but
	 * since the pointers are generic
	 * we fake it
	 */
	return((piv - (BYTE *) first)/size);
}