getturningpoint.java

The running time of quicksort can be improved in practice by taking advantage of the fast running t

import javax.swing.JOptionPane;

public class GetTurningPoint
{
	public static void main(String[] args) 
	{
		//Input the range of the length of the array.
		String strLeftBound = JOptionPane.showInputDialog(null, "Enter the left bound of the range of key:", "Input", JOptionPane.QUESTION_MESSAGE);
		String strRightBound = JOptionPane.showInputDialog(null, "Enter the right bound of the range of key:", "Input", JOptionPane.QUESTION_MESSAGE);
		int leftBound = 0;
		int rightBound = 0;
		try
		{
			leftBound = Integer.parseInt(strLeftBound);
			rightBound = Integer.parseInt(strRightBound);
		}
		catch (Exception e)
		{
			JOptionPane.showMessageDialog(null, "Please enter an integer!", "Error", JOptionPane.WARNING_MESSAGE);
			System.exit(0);
		}

		//Find the turning point.
		for (int k = leftBound; k <= rightBound; k ++)
		{
			long timeSpentByInsertionSort = 0;
			long timeSpentByQuickSort = 0;

			//Also do the experiment one million times in order to reduce the coincidence.
			for (int m = 1; m <= 1000000; m ++)
			{
				double[] sourceArrayForInsertionSort = new double[k];
				double[] sourceArrayForQuickSort = new double[k];
				for (int n = 0; n < sourceArrayForInsertionSort.length; n ++)
					sourceArrayForInsertionSort[n] = Math.random();
				for (int n = 0; n < sourceArrayForQuickSort.length; n ++)
					sourceArrayForQuickSort[n] = sourceArrayForInsertionSort[n];

				Sort insertionSort = new Sort(sourceArrayForInsertionSort);
				long startTime = System.nanoTime();
				insertionSort.insertionSort(0, sourceArrayForInsertionSort.length - 1);
				timeSpentByInsertionSort += System.nanoTime() - startTime;

				Sort quickSort = new Sort(sourceArrayForQuickSort);
				startTime = System.nanoTime();
				quickSort.quickSort(0, sourceArrayForQuickSort.length - 1);
				timeSpentByQuickSort += System.nanoTime() - startTime;
			}

			//Output the result when quick sort is faster than insertion sort at the first time.
			if (timeSpentByInsertionSort > timeSpentByQuickSort)
			{
				System.out.println("When the length of array is " + k  + ", insertion sort is about as quick as quick sort.");
				break;
			}
		}
	}
}