// This is the quiz version of sortDemos -- it has
// quicksort and mergesort removed.  Your task is to
// replace them with the correct code.

class SortQuiz
{
	///////////////////////////////////////////////
	/// 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
	///////////////////////////////////////////////

	public static void quicksort(int[] a)
	{
		// YOU WRITE THIS!!!
	}

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

	public static void mergesort(int[] a)
	{
		// YOU WRITE THIS!!!
	}

	///////////////////////////////////////////////
	/// 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();
	}		

}