//quickSort.java
/*---------------------------------------------------------------
' class quickSort for package sort
'
' DESC: This sort runs at an average of nlogn passes, though in worst case scenerios
'       with arrays that are already sorted (descending or ascending order) it can run
'	  at pow(n,2) passes.  For this package int arrays are used.  This can easily 
'       be changed to accept float, double or long arrays.  Just change the paramenter 
'       variables (and others) from int to what you want. 
' 
' NOTE: Since JDK 1.2, Java uses a tuned-up version of quickSort in the java.util.Arrays
'	  package.
'	  This class was inspired by James Gosling's implementation of the quickSort on 
'       java.sun.com and several other implementations.  This version handles arrays with
'       non-unique numbers.  
'
' CONSTRUCTOR: NOT USED 
'
' METHODS:
'	sort(int array[]) -- public, static
'     	DESC: takes int array in and then passes it to overloaded method.                
'		RETURN: VOID
'	sort(int array[], int start, int end) -- public, static
'		DESC: takes array in and then sorts the array in ascending order using a quickSort '			algorithm.
'		RETURN: VOID
'	partition (int array[], int lo, int hi) -- protected, static
'           DESC: this method is called by sort and it does 
' 			the majority of the work by picking the pivot, transvering the array and '			swapping appropriate values.
'		RETURN: int hi
'	printArray(int array[]) -- public, static
'		DESC: print the array out using System.out.print statement.
'		RETURN: VOID
'
' DATE MODIFIED:	 10/28/2000
' VERSION:		 1.0
'----------------------------------------------------------------
*/	

package sort;

public class quickSort {

public static void sort(int array[]) throws Exception 
{ 
	sort(array, 0, array.length - 1); 
} // end of sort method

public static void sort(int array[], int start, int end) 
{
	int p; 
	if (end > start) 
	{ 
		p = partition(array, start, end); 
		sort(array, start, p-1); 
		sort(array, p+1, end); 
	} // end of if
} // end of sort method

protected static int partition (int array[], int lo, int hi)
{

	int hi0 = hi; 

      //Pick a pivot from the middle and move it out of the way 
      //a pivot could also be picked by using a median-of-three formula
	//I might put this in later.
	int pivot = array[(lo + hi) / 2];
      array[(lo + hi) / 2] = array[hi];
      array[hi] = pivot;

	while (lo < hi) {
	    	while (lo<hi && array[lo] <= pivot) {
			lo++;
	      } //end of while
		while (lo<hi && array[hi] >= pivot) {
			hi--;
	    	} //end of while
	    	if (lo < hi) {
			//change int T, if type of array changes.
			int T = array[lo];
			array[lo] = array[hi];
			array[hi] = T;
		} // end of if
	} // end of while
	
      //Put the median in the center of the list
      array[hi0] = array[hi];
      array[hi] = pivot;
	
	return hi;
} // end of partition method

public static void printArray (int array[])
	{
		System.out.print("\n");
		for (int i = 0; i < array.length; ++i)
		{
			System.out.print(array[i]);
			if (i != array.length-1)
				System.out.print(",");
			else
				System.out.print("\n");
		} //end of for statement
	} // end of printArray method

} // end of quickSort class