/*
   Quicksort that sorts doubles using an explicit recursion stack.

   In the worst case (an inversely sorted stack), quicksort is O(n*n),
   and using the runtime stack as the recursion stack may cause overflow.
   So we need to implement the stack manually as a data structure inside our
   program.  We're simply implementing recursion at a more primitive level
   by duplicating what should happen with the runtime stack.

*/

// manually managed recursion stack:
class stack
{
    public int x;  // used to record starting index of partion
    public int y;  // last index (inclusive) of partition.
    public stack tail;
    public stack(int a, int b, stack t) {x=a; y=b; tail=t;}
}


public class quickdouble
{
    public double[] A;  // pointer to 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*100; }
    } // constructor
    
    // alternate constructor takes pointer to existing array:
    public quickdouble(double[] B) {A = B;}
    

    public void print() // prints array - don't call on very large arrays!
    {
	for(int i=0;i<A.length;i++) System.out.printf("%.3f ",A[i]);
	System.out.print("\n");
    }    


    // 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) // end index inclusive
    {
	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

    // main routine:
    public void qsort(int start, int end)
    {
	stack RS = new stack(start,end,null);
	while (RS != null)
	    {
		start = RS.x;  end = RS.y;  // take parameters off of stack
		RS = RS.tail;  // pop stack
		int pi = findpivot(start,end); 
		if (pi>=0)  // pivot exists
		{
		  int start2 = partition(start,end,pi); 
		  RS = new stack(start,start2-1,RS); // push 1st partition
		  RS = new stack(start2,end,RS);     // push 2nd partition
		}
	    } // while
    }//qsort


    /*    test main     UNCOMMENT to run test: */

    public static void main(String[] args)
    {
	int n = Integer.parseInt(args[0]);  // length of array to be created
	long t1, t2;  // 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

// sample run:
//$ java -Xmx1024m quickdouble 50000000