public class QuickSort extends Sorter
{	
	public int medianOfThree(int[] F, int u, int o)
	{
		int m = (u + o) / 2;
		
		if (F[u] > F[m]) swap(F, u, m);
		if (F[u] > F[o]) swap(F, u, o);
		if (F[m] > F[o]) swap(F, m, o);

		swap(F, m, o-1);
		return o-1;
	}
	
	public int partition(int[] F, int u, int o, int p)
	{
		int pn = u; int pv = F[p];
		swap(F, p, o);
		for (int i = u; i < o-1; i++)
		{
			if (compare(pv, F[i]))
			{
				swap(F, pn, i);
				pn = pn+1;
			}
		}
		swap(F, o, pn);
		return pn;
	}
	
	public void quicksort(int[] F, int u, int o)
	{
		if (o > u)
		{
			int p  = medianOfThree(F, u, o);
			int pn = partition(F, u, o, p);
			quicksort(F, u, pn-1);
			quicksort(F, pn+1, o);
		}
	}
	
	public int[] sort(int[] F)
	{
		quicksort(F, 0, F.length-1);
		return F;
	}
	
	public static void main(String[] args)
	{
		int[] F       = ArrayHelper.initArray();
		QuickSort QS  = new QuickSort();
		System.out.println(ArrayHelper.toString(F));
		System.out.println(ArrayHelper.toString(QS.sort(F)));
	}
}