advancedsort.java

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

public class AdvancedSort 
{
	private double[] sourceArray;
	private double[] targetArray;
	final private int TURNINGPOINT;					//The final variable to store the turning point.
	private double key;
	private static int flag;

	public AdvancedSort(double[] sourceArray)
	{
		this.sourceArray = sourceArray;
		TURNINGPOINT = 102;
		targetArray = new double[sourceArray.length];
		flag = 0;
	}

	//Estimate whether the length of array is larger than the turning point at first.
	public void sort()
	{
		if (sourceArray.length < TURNINGPOINT)
			insertionSort(0, sourceArray.length - 1);
		else
			quickSort(0, sourceArray.length - 1);
	}

	/* The method to output the result. */
	public void result()
	{
		for (int n = 0; n < targetArray.length; n ++)
			System.out.println(targetArray[n]);
	}

	/* Insertion sort */
	private void insertionSort(int leftBound, int rightBound)
	{
		double key = 0;
		int i = leftBound;
		for (int j = leftBound + 1; j <= rightBound; j++ )
		{
			key = sourceArray[j];
			i = j ;
			while (i > leftBound && sourceArray[i - 1] > key)
			{
				sourceArray[i] = sourceArray[i - 1];
				i --;
			}
			sourceArray[i] = key;
		}

		for (int n = leftBound; n <= rightBound; n ++)
		{
			targetArray[flag] = sourceArray[n];
			flag ++;
		}
	}

	/* Quick sort */
	private void quickSort(int leftBound, int rightBound)
	{
		if (leftBound < rightBound)
		{
			int newBound = partition(leftBound, rightBound);
			if (leftBound - newBound + 1 < TURNINGPOINT)
				insertionSort(leftBound, newBound - 1);
			else
				quickSort(leftBound, newBound - 1);
			combine(newBound);
			if (newBound - rightBound + 1 < TURNINGPOINT)
				insertionSort(newBound + 1, rightBound);
			else
				quickSort(newBound + 1, rightBound);
		}
		else if (leftBound == rightBound)
			combine(leftBound);
	}

	private int partition(int leftBound, int rightBound)
	{
		int i = leftBound - 1;

		for (int j = leftBound; j <= rightBound - 1; j ++)
			if (sourceArray[j] <= sourceArray[rightBound])
			{
				i ++;
				exchange(i,j);
			}
		exchange(i + 1, rightBound);
		return i + 1;
	}

	private void exchange(int i, int j)
	{
		double temp = sourceArray[i];
		sourceArray[i] = sourceArray[j];
		sourceArray[j] = temp;
	}

	private void combine(int i)
	{
		targetArray[flag] = sourceArray[i];
		flag ++;
	}
}