package CW4;

import java.util.*;

public class JavaAlgosCW4 {
	public static final int partitionOne(int[] a, int left, int right)
	{
		int pivot = right;
		int i = left, j = right;

		while( i < j )
		{
			if ( a[i] <= a[pivot] )
			{
				i++;
				System.out.println("Stage 1 // I: " + i);
			}
			if( a[i] > a[pivot])
			{
				if(( a[i] > a[pivot] ) && ( a[j] <= a[pivot] ))
				{
					swapIndex(a,i,j);
					i++;
				}
				if( a[j] > a[pivot])
				{
					j--;
					System.out.println("Stage 2 // J: " + j);
				}
			}

			if ( i < j )
			{
				swapIndex(a,i,j);
				System.out.println("Stage 3 // Swap: "
						+ " a[i="+i+"] = " + a[i]
						+ " a[j="+j+"] = " + a[j]
						+ Arrays.toString(a));
			}
		}
		swapIndex(a,i,pivot);
		return i;
	}

	public static final int partitionTwo(int[] a, int left, int right)
	{
		int p = medianOfThree(a,left,(right/2),right);
		int pivot = right;
		int i = left, j = right;

		while( i < j )
		{
			if ( a[i] <= a[pivot] )
			{
				i++;
				System.out.println("Stage 1 // I: " + i);
			}
			if( a[i] > a[pivot])
			{
				if(( a[i] > a[pivot] ) && ( a[j] <= a[pivot] ))
				{
					swapIndex(a,i,j);
					i++;
				}
				if( a[j] > a[pivot])
				{
					j--;
					System.out.println("Stage 2 // J: " + j);
				}
			}

			if ( i < j )
			{
				swapIndex(a,i,j);
				System.out.println("Stage 3 // Swap: "
						+ " a[i="+i+"] = " + a[i]
						+ " a[j="+j+"] = " + a[j]
						+ Arrays.toString(a));
			}
		}
		swapIndex(a,i,pivot);
		return i;
	}

	private static final void swapIndex(int[] a, int index1, int index2)
	{
		int temp = a[index1];
		a[index1] = a[index2];
		a[index2] = temp;
	}

	public static void quicksort(int[] a, int i, int j)
	{
		if(i>=j)
		{
			return;
		}
		int p = partitionOne(a, i, j);
		quicksort(a, i, p-1);
		quicksort(a, p+1, j);
	}
	private static int medianOfThree (Comparable[] a, int left, int mid, int right) {
	/* Return median position in array of elements
	* a[left], a[mid], and a[right] */
	if (a[left].compareTo(a[mid]) < 0) {
		if (a[mid].compareTo(a[right]) < 0)
			return mid;
		else if(a[left].compareTo(a[right]) < 0)
			return right;
		else
			return left;
	} else {
		if (a[mid].compareTo(a[right]) > 0)
			return mid;
		else if (a[left].compareTo(a[right]) > 0)
			return right;
		else
			return left;
	}

	public static void main(String[] args)
	{
		//int[] numbers = {9,8,7,6,5,4,3,2,1};
		int[] numbers = {24,2,45,20,56,100,2,56,99,53,12};

		System.out.println(Arrays.toString(numbers));
		JavaAlgosCW4.quicksort(numbers, 0, numbers.length - 1);
		System.out.println(Arrays.toString(numbers));
	}
}