/*
 * $Id$
 * $Log$
 */

/*
 * quick sort with median value selection.
 * QuickMSortAlgorithm.java
 */
public class QuickMSortAlgorithm extends SortAlgorithm 
	{
	/* 
	 * This is a generic version of the quick sort
	 * algorithm.
	 *
	 * @param a		 an integer array
	 * @param lo	left boundary of array partition
	 * @param hi	right boundary of array partition
	 */
	public void QuickMSortAlgorithm(int a[], int lo, int hi)
		throws Exception
		{
		int pivot;
		int l = lo;
		int h = hi;
		int m = (hi+lo)/2;

		if ( hi - lo <= 0)	// only one item...
			return;

		/*
		 *	find median-of-three-points.
		 *	(to explore: inheritance, with only different pvt fct?
		 */
		pause (lo, hi);
		if ( a[lo] <= a[m] && a[m] <= a[hi] )
			pivot = a[m];
		else if ( a[hi] <= a[m] && a[m] <= a[lo] )
			{
			swap (a, lo, hi);
			pivot = a[m];
			}
		else if ( a[m] <= a[lo] && a[lo] <= a[hi] )
			{
			swap (a, lo, m);
			pivot = a[lo];
			}
		else if ( a[hi] <= a[lo] && a[lo] <= a[m] )
			{
			swap (a, lo, m);
			swap (a, lo, hi);
			pivot = a[lo];
			}
		else if ( a[lo] <= a[hi] && a[hi] <= a[m] )
			{
			swap (a, hi, m);
			pivot = a[hi];
			}
		else
			{
			swap (a, m, hi);
			swap (a, lo, hi);
			pivot = a[hi];
			}

		++l;
		--h;

		/*
		 *	Partition array
		 */
		while ( l <= h )
			{
			while ( l < hi && a[l] < pivot )
				{
				pause (l, h);
				++l;
				}

			while ( lo < h && a[h] > pivot )
				{
				pause (l, h);
				--h;
				}

			if ( l <= h )
				{
				swap (a, l, h);
				++l;
				--h;
				}
			}

		/*
		 *	Recursive calls
		 */
		if (lo < h)
			QuickMSortAlgorithm (a, lo, h);
		if (h < hi)
			QuickMSortAlgorithm (a, l, hi);
		} 

	private void swap(int a[], int i, int j)
		{
		int T;
		T = a[i]; 
		a[i] = a[j];
		a[j] = T;
		}

	public void sort(int a[]) throws Exception
		{
		QuickMSortAlgorithm(a, 0, a.length - 1);
		pause (-1, -1);
		}
	}