// Andrew Martin
// Sample of a Quicksort without using Recursion
//   I restricted this to integers to simplify the example.

public class QuicksortWithRecursion
{
	public static void main (String[] args)
	{
		int[] intsToSort = {18, 79, 25, 59, 83, 60, 55, 43, 78, 73, 16, 85, 6, 17, 9, 32, 65, 67, 8, 11, 29, 74, 38, 94, 24, 87, 99, 36, 52, 32, 92, 83, 84, 81, 91};
		System.out.println("Before sorting:");
		for (int i = 0; i < intsToSort.length; i++)
			System.out.print(intsToSort[i] + " ");
			
		quicksort(intsToSort, 0, intsToSort.length-1);
		
		System.out.println("\n\nAfter sorting:");
		for (int i = 0; i < intsToSort.length; i++)
			System.out.print(intsToSort[i] + " ");
		System.out.println("");
	}
	
	public static void quicksort(int[] toSort, int beginning, int end)
	{
		// This is the recursive method of this class.  It calls partition on the left side
		// of the tree then fills in the right side.
		if (beginning < end)
			{
				int pivotIndex = partition(toSort, beginning, end);
				
				quicksort(toSort, beginning, pivotIndex - 1);
				quicksort(toSort, pivotIndex + 1, end);
			}
	}
	
	public static int partition (int[] toSort, int beginning, int end)
	{
		// This is the main sorting method of the class.  The integer it returns is 
		// in place in the sort, that is everything with a smaller index has a smaller
		// value, and everything with a larger index has a larger value.
		int endValue = toSort[end];
		int pivotIndex = beginning - 1;
		for (int i = beginning; i < end; i++)
		{
			if (toSort[i] <= endValue)
			{
				pivotIndex++;
				swapPlaces(toSort, pivotIndex, i);
			}
		}
		swapPlaces(toSort, pivotIndex + 1, end);

		return pivotIndex + 1;
	}
	
	public static void swapPlaces (int[] toSwap, int first, int last)
	{
		// This is just a simple method to cut down on some typing on all the swaps
		// It simply swaps the two values at the two indices passed in the array that's passed.
		int temp = toSwap[first];
		toSwap[first] = toSwap[last];
		toSwap[last] = temp;
	}
}