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

/*
 * quick sort
 * QuickSortAlgorithm.java
 */
public class QuickSortAlgorithm extends SortAlgorithm 
	{
	/* 
	 * This is a generic version of the quick sort
	 * algorithm.
	 *
	 * Quick sort is a 'divide-and-conquer' algorithm.
	 * 
	 * @param a		 an integer array
	 * @param lo	left boundary of array partition
	 * @param hi	right boundary of array partition
	 */
	public void QuickSortAlgorithm(int a[], int lo, int hi)
		throws Exception
		{
		int pivot = a[(hi+lo) / 2];
		int l = lo;
		int h = hi;

		if ( lo == hi )
			return;

		/*
		 *	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)
			QuickSortAlgorithm (a, lo, h);
		if (h < hi)
			QuickSortAlgorithm (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
		{
		QuickSortAlgorithm(a, 0, a.length - 1);
		pause (-1, -1);
		}
	}