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

import java.util.*;
import java.lang.*;

public class QuicksortWithoutRecursion
{
	public static void main (String[] args)
	{
		int[] intsToSort = {16, 85, 6, 17, 9, 32, 65, 67, 8, 11, 29, 74, 38, 94, 24, 87, 99, 36, 52, 32, 92, 83, 84, 81, 52};		

		System.out.println("Before sorting:");
		for (int i = 0; i < intsToSort.length; i++)
			System.out.print(intsToSort[i] + " ");			
		System.out.println("");	
		System.out.println("");	
		
		quicksort(intsToSort);
		
		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)
	{
//		This method starts the Partition method and the re-runs partition on smaller and smaller subsets.  It 
//		works down the left side of the tree until it's done and then works the remaining right sides.

		Stack pivotStack = new Stack();
		int beginning = 0;
		int end = toSort.length - 1;
		
		pivotStack.push(partition(toSort, beginning, end));
		
		while (!pivotStack.isEmpty())	//  This while keeps it picking new indices until the stack is empty.
		{
			while (objToInt(pivotStack.peek()) - beginning <= 1)	// if there are no more values to test, start on the smallest right side.
			{
				beginning = objToInt(pivotStack.pop()) + 1;		// the beginning value is changed to the smallest unsorted value
				
				if (!pivotStack.isEmpty())						// this one was tricky, getting the loops to end at the right time
					end = objToInt(pivotStack.peek()) - 1;		//  If the stack isn't empty then the end index is changed
				else
				{
					if (beginning >= toSort.length)				// If the stack is empty, then either end is changed to the last index
					break;										// or it's kicked out of the loop if beginning has surpassed it.
					pivotStack.push(toSort.length);
				}
			}
			if (!pivotStack.isEmpty())
				end = objToInt(pivotStack.peek()) - 1;
			if (beginning < toSort.length - 1)
				pivotStack.push(partition(toSort, beginning, 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;
	}
	
	public static int objToInt (Object obj)
	{
		// This method simply converts the passed Object into an integer
		// This one got me, I assumed that when I put an integer on the stack it would 
		// stay as an integer, but it gets treated as a plain Object when on the stack.
		// It makes sense, but I didn't realize that was how it worked in the beinning. 
		int tempInt = ((Integer)obj).intValue();
		return tempInt;
	}
}