/*
   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.

*/

class stack  // recursion stack class to avoid worst-case behavior
{
    public int x;
    public int y;
    public stack tail;
    public stack(int a, int b, stack t) {x=a; y=b; tail=t;}
}


public class quickdouble
{
    public 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*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.print(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

    public void qsort()
    {
	int start = 0, end = 0;
	stack RS = new stack(0,A.length-1,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); // 1st recursion
		  RS = new stack(start2,end,RS);     // 2nd recursion
		}
	    } // 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, t3;  // for timing comparisons
	quickdouble qsinstance = new quickdouble(n);
	
	t1 = System.currentTimeMillis();
        qsinstance.qsort();
	t2 = System.currentTimeMillis();

	System.out.println("time to quicksort : "+(t2-t1)+"ms");
	
	//qsinstance.print();  // do not use during timing tests
    } // main

    */
} // quickdouble