/* quicker.c --  Improved Quicksort algorithm	*/

/*
 *  The Quicksort algorithm was invented in 1960 by C. A. R. Hoare.  Since  *
 *  then, it has been analyzed and studied by many people,  it is probably  *
 *  the  most  thoroughly  analyzed  of  any  of  the  sorting algorithms.  *
 *  Numerous "improvements" to the basic Qicksort algorithm have  appeared  *
 *  in  the  literature  however  only  a  few  have  real  benefit.   The  *
 *  "improvements" in this implementation have  been  documented  by  many  *
 *  people  but  I followed Robert Sedgewick as presented in his excellent  *
 *  book, "Alogrithms in C", published by Addison Wesley.                   *
 *                                                                          *
 *  The first of the improvements is to always sort the smaller  partition  *
 *  first.  Without  this improvement,  Quicksort can be as slow as Bubble  *
 *  sort in the worst case (a file that is already in sort  order  in  the  *
 *  worst  case  for Quicksort).  The second improvement is to change from  *
 *  the  original  recursive  algorithm  to  an  iterative  algorithm.  By  *
 *  ensuring  that the smaller partition is always sorted first and by not  *
 *  putting the smaller partition on the stack ("end recursion  removal"),  *
 *  we ensure that we need room on the stack for only about log N entries.  *
 *                                                                          *
 *  Another  improvement  used  is to use an insertion sort for partitions  *
 *  less  than  some  rather  arbitrary  size.  Sedgewick  says  that  the  *
 *  algorithm works about the same for sizes from 5 entries to 25 entries.  *
 *  This implementation used 9.                                             *
 *                                                                          *
 *  The  final  improvement  is  to use a "median of three" as the pivotal  *
 *  element.                                                                *
 *                                                                          *
 *  Sedgewick says that the combination of these improvements  results  in  *
 *  an algorithm that is 25% to 30% faster than the basic algorithm on the  *
 *  average.                                                                *
 */

#define M 9

extern int      (*comp) (const void *a, const void *b);
static void     Sift(char *Array[], int n,
					int (*comp) (const void *a, const void *b));
static void     Exchange(char *Array[], register int i, register int j);

 void
quicksort (char *Array[], int Count, int Width,
		  int (*comp) (const void *a, const void *b)) {
	char           *Pivot;
	register int    Left = 0;
	register int    Right;
	register int    i, j;
	register int    StkPtr = 0;

	struct {
		int             Left;
		int             Right;
		}               Stack[32];

	Right = Count - 1;
	while (1) {
		if ((*comp) (&Array[Left], &Array[Right]) > 0)
			Exchange(Array, Left, Right);
		if ((*comp) (&Array[((Left + Right) / 2)], &Array[Right]) > 0)
			Exchange(Array, ((Left + Right) / 2), Right);
		if ((*comp) (&Array[Left], &Array[((Left + Right) / 2)]) > 0)
			Exchange(Array, Left, ((Left + Right) / 2));
		Exchange(Array, (Left + 1), ((Left + Right) / 2));
		i = Left + 1;
		j = Right;
		Pivot = Array[(Left + 1)];
		while (1) {
			while ((*comp) (&Array[++i], &Pivot) < 0);
			while ((*comp) (&Array[--j], &Pivot) > 0);
			if (i >= j) break;
			Exchange(Array, i, j);
			}
		Exchange(Array, Left, j);
		if (j - Left > Right - j) {
			if (M >= j - Left) {
				if (StkPtr == 0) break;
				StkPtr++;
				Left = Stack[StkPtr].Left;
				Right = Stack[StkPtr].Right;
				}
			else {
				if (Right - j > M) {
					Stack[StkPtr].Left = Left;
					Stack[StkPtr].Right = j - 1;
					StkPtr++;
					Left = j + 1;
					}
				else Right = j - 1;
				}
			}
		else {
			if (M >= Right - j) {
				if (!StkPtr) break;
				StkPtr--;
				Left = Stack[StkPtr].Left;
				Right = Stack[StkPtr].Right;
				}
			else {
				if (j - Left > M) {
					Stack[StkPtr].Left = j + 1;
					Stack[StkPtr].Right = Right;
					StkPtr++;
					Right = j - 1;
					}
				else Left = j + 1;
				}
			}
		}
	Sift(Array, Count, comp);
	}

 static void
Sift (char *Array[], int Count, int (*comp) (const void *a, const void *b)) {
	register int    i, j;
	char           *c;

	for (j = 1; j < Count; ++j) {
		i = j - 1;
		c = Array[j];
		while ((*comp) (&c, &Array[i]) < 0) {
			Array[(i + 1)] = Array[i];
			if (--i < 0) break;
			}
		Array[(i + 1)] = c;
		}
	}


/*
 * Given an Array[] of pointers to char, exchange its ith and jth elements.
 */
 static void
Exchange (char *Array[], register int i, register int j) {
	char           *temp;

	temp = Array[i];
	Array[i] = Array[j];
	Array[j] = temp;
	}