// pacs, 3/27 and 3/28
// in-class code for hw14 and hw15
// warning:  this code was developed in class and MAY HAVE ERRORS.
// you are responsible for the correct versions of this code,
// regardless of any small errors which may be in the code below.

class HW14
{
	///////////////////////////////////////////////
	/// swap
	///////////////////////////////////////////////
	
	// swap a[i] with a[j]
	public static void swap(int[] a, int i, int j)
	{
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	///////////////////////////////////////////////
	/// quicksort
	///////////////////////////////////////////////

	// lo and hi are INDEXES, and we are going to sort
	// a from a[lo] to a[hi]
	public static void quicksort(int[] a, int lo, int hi)
	{
		// BASE CASE
		if (lo >= hi)
			// lo has equalled (or crossed) hi, so we have
			// either a singleton or an empty array, either
			// way, it is sorted
			return;
		// first, set the pivot to the first element
		int pivot = a[lo];
		// now, keep pivoting until the left and right indexes cross
		int leftIndex = lo + 1;
		int rightIndex = hi;
		while (rightIndex > leftIndex)
		{
			// 1. if the element on the right is in the right place,
			// move the rightIndex one to the left
			if (a[rightIndex] > pivot)
				rightIndex--;
			
			// 2. else if the element on the left is in the right place,
			// move the leftIndex one to the right
			else if (a[leftIndex] <= pivot)
				leftIndex++;
			
			// 3. otherwise, both sides are wrong, so SWAP them
			else
				swap(a,leftIndex,rightIndex);
		}
		// at this point, leftIndex and rightIndex equal each
		// other, and the pivot is stored in a[lo].
		// We now want to swap the pivot (a[0]) with the last
		// element on the left.  This will either be the element
		// where the two indexes met, or the one just to its left.
		int newPivotIndex;
		if (a[leftIndex] > pivot)
			newPivotIndex = leftIndex - 1;
		else
			newPivotIndex = leftIndex;
		// now just swap the pivot into its new location
		swap(a,lo,newPivotIndex);
		// now recursively sort the left and right sides, being
		// sure not to sort the pivot again!
		quicksort(a,lo,newPivotIndex-1);
		quicksort(a,newPivotIndex+1,hi);
	}
	
	public static void quicksort(int[] a)
	{
		quicksort(a,0,a.length-1);
	}

	///////////////////////////////////////////////
	/// mergesort
	///////////////////////////////////////////////

	// lo and hi are INDEXES, and we are going to sort
	// a from a[lo] to a[hi]
	public static void mergesort(int[] a, int lo, int hi, int[] copy)
	{
		int mid = (lo + hi)/2;
		// step 0 -- BASE CASE
		if (lo >= hi)
			// lo has equalled (or crossed) hi, so we have
			// either a singleton or an empty array, either
			// way, it is sorted
			return;
		// step 1 -- sort the left half
		mergesort(a,lo,mid,copy);
		// step 2 -- sort the right half
		mergesort(a,mid+1,hi,copy);
		// step 3 -- merge the two sorted halves
		int leftIndex, rightIndex, copyIndex;
		leftIndex = lo;
		rightIndex = mid+1;
		for (copyIndex = lo; copyIndex <= hi; copyIndex++)
		{
			// if there are no more elements on the left, use
			// the right side.  Or, if there are elements on
			// the right and the right is smaller, still use
			// the right side.
			if ((leftIndex > mid) ||
			    ((rightIndex <= hi) && (a[rightIndex] < a[leftIndex])))
			{
				// use the right
				copy[copyIndex] = a[rightIndex];
				rightIndex++;
			}
			else
			{
				// use the left
				copy[copyIndex] = a[leftIndex];
				leftIndex++;
			}
		}
		// step 4 -- put the copy back into a
		for (copyIndex = lo; copyIndex <= hi; copyIndex++)
			a[copyIndex] = copy[copyIndex];
	}
	
	public static void mergesort(int[] a)
	{
		int[] copy = new int[a.length];
		mergesort(a,0,a.length-1,copy);
	}

	///////////////////////////////////////////////
	/// insertionsort
	///////////////////////////////////////////////
	
	public static void insertionsort(int[] a)
	{
		for (int i = 0; i < a.length; i++)
			for (int j = 0; j < i; j++)
				if(a[i] < a[j])
					swap(a,i,j);
	}

	///////////////////////////////////////////////
	/// selectionsort
	///////////////////////////////////////////////

	public static void selectionsort(int[] a)
	{
		for (int i = 0; i < a.length; i++)
			for (int j = i + 1; j < a.length; j++)
				if (a[i] > a[j])
					swap(a,i,j);
	}
	
	///////////////////////////////////////////////
	/// bubblesort
	///////////////////////////////////////////////

	public static void bubblesort(int[]a)
	{
		boolean didSwap = true;
		while (didSwap == true)
		{
			didSwap = false;
			for (int i = 0; i < a.length - 1; i++)
			{
				if (a[i] > a[i + 1])
				{
					swap(a,i,i + 1);
					didSwap = true;
				}
			}
		}
	}
	
	///////////////////////////////////////////////
	/// sortArray, randomArray, printArray
	///////////////////////////////////////////////

	public static void sortArray(int[] a, String sort)
	{
		if (sort.equals("bubble"))
			bubblesort(a);
		else if (sort.equals("insertion"))
			insertionsort(a);
		else if (sort.equals("selection"))
			selectionsort(a);
		else if (sort.equals("merge"))
			mergesort(a);
		else if (sort.equals("quick"))
			quicksort(a);
		else
			System.out.println("**** UNKNOWN SORT: " + sort + " ****");
	}
	
	public static int[] makeRandomArray(int arraySize)
	{
		int[] a = new int[arraySize];
		for (int i = 0; i < arraySize; i++)
			a[i] = (int)(100000 * Math.random());
		return a;
	}
	
	// prints in integer right-justified in an 6-character-wide field
	public static void printInteger(int x)
	{
		// first, convert x to a String
		String output = new Integer(x).toString();
		// next, print out as many leading spaces as necessary
		for (int i=output.length();i<6;i++)
			System.out.print(" ");
		// finally, print out the number
		System.out.print(output);
	}
	
	// prints the array, 10 elements per line
	public static void printArray(int[] a)
	{
		for (int i = 0; i<a.length; i++)
		{
			if (i % 11 == 10)
				System.out.println();
			printInteger(a[i]);
		}
		System.out.println();
	}
	
	///////////////////////////////////////////////
	/// getCommand and main
	///////////////////////////////////////////////

	public static int getCommand(String[] sorts, int currentSort,
								 boolean doPrint)
	{
		int command, sort;
		System.out.println("--------------------");
		System.out.println("Now using:  " + sorts[currentSort] + "sort");
		System.out.println("Printing is " + (doPrint ? "on" : "off"));
		System.out.println("Commands:");
		System.out.println("  <0: exit");
		for (sort=0;sort<sorts.length;sort++)
			System.out.println("   " + sort + ": " + sorts[sort] + "sort");
		System.out.println("   " + sorts.length + ": toggle printing");
		System.out.println("  >" + sorts.length + ": set array size and sort");
		System.out.print("Enter command: ");
		command = readInt();
		System.out.println("--------------------");
		return command;
	}
	
	public static void main(String[] args)
	{
		int arraySize, currentSort = 0;
		long time1, time2;
		boolean doPrint = true;
		String[] sorts = {"bubble","insertion","selection","merge","quick"};
		while (true)
		{
			int command = getCommand(sorts,currentSort,doPrint);
			if (command < 0)
				// command = exit
				break;
			else if (command < sorts.length)
				// command = new sort, command is the index into sorts array
				currentSort = command;
			else if (command == sorts.length)
				// command = toggle printing
				doPrint = !doPrint;
			else
			{
				// command = create and sort array, command is array size
				arraySize = command;
				int[] array = makeRandomArray(arraySize);
				
				if (doPrint)
				{
					System.out.println("before:");
					printArray(array);
				}
				
				time1 = System.currentTimeMillis();
				sortArray(array,sorts[currentSort]);
				time2 = System.currentTimeMillis();
				
				if (doPrint)
				{
					System.out.println("after:");
					printArray(array);
				}
				
				System.out.println("Total sort time:  "
									+ (time2 - time1) + " milliseconds");
			}
		}
		System.out.println("Goodbye!");
	}

	///////////////////////////////////////////////
	/// readString, readInt, readDouble
	///////////////////////////////////////////////

	public static String readString()
	{
		String result="";
		char c;
		try 
		{
			while(true)
			{
				c = (char)System.in.read();
				if(!Character.isWhitespace(c))
					break;
			}
			while(true)
			{
				result += c;
				c = (char)System.in.read();
				if(Character.isWhitespace(c))
					break;
			}
		}
		catch (java.io.IOException e)
		{
			System.out.println("Error while reading string.");
			result += "_ERROR_";
		}
		return result;
	}
	public static int readInt()
	{
		return Integer.parseInt(readString());
	}
	public static double readDouble()
	{
		return Double.valueOf(readString()).doubleValue();
	}
			
}