/*
  The quicksort algorithm is the most often used algorithm for sorting arrays.  It
also illustrates well the concepts of recursion and the difference between average
and worst-case complexity measures.  Quicksort is average case O(n*log n) and worst
case O(n*n).
*/


public class quicksort
{
    private double[] A;  // array to be sorted.

    public quicksort(int n) // constructor generates random array of size n
    {
	A = new double[n];
	for (int i=0;i<n;i++)  
	    { A[i] = Math.random(); }
    } // constructor
    
    public void print() // prints array - don't call on very large arrays!
    {
	for(int i=0;i<A.length;i++) System.out.print(A[i]+" ");
	System.out.print("\n");
    }    

    /* Bubblesort algorithm for comparison  */
    public void bsort()
    {
	int i, j;
	int n = A.length;
	double temp; 
	for(i=0;i<n-1;i++)
	    for(j=0;j<n-1-i;j++)
		{
		    if (A[j]>A[j+1])
			{
			    temp = A[j];
			    A[j] = A[j+1];
			    A[j+1] = temp;
			}
		} // nested for
    } // bsort

    /*
      The quicksort algorithm will be implemented using three procedures:
  
        findpivot : locates the first element out of order in an array segment
        partition : partitions an array segment into two halves using pivot
	qsort     : main recursive procedure that uses findpivot and partition.


	The trickiest of these procedures is paritition.  To understand how it works,
        consider the array segment
	
	     3 5 6 4 9 2
	     
	The pivot is 4, the first element not in order.  To divide the paritition,
	we use two index values, i and e.  i is used to simply step through each
	element of the array.  e is used to keep track the end of the first partition,
	were every element should be <= pivot.  Fortunately, if the pivot exists then
	we know that neither partition will be empty.  Going through the array, whenever
	we find an element that's <= pivot, we swap it with A[e] and increment e.  
	Thus at the end of our loop, every element to the left of index e will be
	<= pivot and e will represent the start index of the second partition.  Tracing
	through this example, you should see that the divided array will become

	   3 4 2  5 9 6

	with e=3.  The 4 was swapped with the 5 and the 2 was swapped with 6.  
	The 3 was swapped with itself when e==i==start.  You can make an optimization 
        to avoid such redundant swaps whenever e==i.  
    */


    // findpivot returns INDEX of 1st element out of order, -1 if non exists.  If
    // no pivot exists, then the array is already sorted
    private int findpivot(int start, int end)
    {
	int i = start;
	while (i<end && A[i]<=A[i+1]) { i++; }
	if (i<end) return i+1; else return -1;
    } //findpivot

    // partition divides array via swapping, and returns start index of 2nd partition
    // The left partition has elements <= pivot, and right one has elements > pivot
    private int partition(int start, int end, int pi)
    {
	double pivot = A[pi]; // records value of pivot (pi is the index)
	int i = start;  // used to step through every element of the array
	int e = start;  // used to keep track of end of first paritition
	double temp;    // used to swap values
	while (i<=end)
	    {
		if (A[i] <= pivot) // swap it to the first partition, inc e
		    {
			temp = A[i];
			A[i] = A[e];
			A[e] = temp;
			e++;
		    }
		i++;
	    } // while
	return e;
    }//parititon

    public void qsort(int start, int end)
    {
	int pi = findpivot(start,end); // find index of pivot, -1 if non exist
	if (pi>=0)  // pivot exists
	    {
		int start2 = partition(start,end,pi); // returns start of 2nd paritition
		qsort(start,start2-1);
		qsort(start2,end);
	    }
	// else partition already sorted, so there's nothing to do
    }//qsort


    /*    test main     */

    public static void main(String[] args)
    {
	int n = Integer.parseInt(args[0]);  // length of array to be created
	long t1, t2, t3;  // for timing comparisons
	quicksort qsinstance = new quicksort(n);
	
	t1 = System.currentTimeMillis();
        if (args[1].equals("quick")) qsinstance.qsort(0,n-1);
   	   else qsinstance.bsort();
	t2 = System.currentTimeMillis();

	System.out.println("time to sort : "+(t2-t1)+"ms");

	//qsinstance.print();  // do not use during timing tests
    } // main


} // quicksort