/*
   Quicksort that sorts doubles.
*/


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

    public quickdouble(int n) // constructor generates random array of size n
    {
	A = new double[n];
	for (int i=0;i<n;i++)  
	    { A[i] = Math.random()*n*10; }
    } // 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");
    }    

    /*
      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
	quickdouble qsinstance = new quickdouble(n);
	
	t1 = System.currentTimeMillis();
        qsinstance.qsort(0,n-1);
	t2 = System.currentTimeMillis();

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

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


} // quickdouble