public class QuickSort {

    static int cnt = 0;
    static int N = 20;
    static double a[] = new double[N];

    static void exch(double[] a, int i, int j){
        double t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    static void compExch(double[] a, int i, int j){
        if( (a[j] < a[i]) )
            exch(a, i, j);
    }

    // logarithmic notation
    //   log N  (not specify base)
    //   ln N   (base e = 2.71823...)
    //   lg N   (base 2)

    // quick sort
    //    worst case  (N^2)/2 comparisons
    //    average case  2N ln N comparisons

    static void quicksort(double[] a, int l, int r){
        if (r <= l) return;
        cnt++;
        int i = partition(a, l, r);
        quicksort(a, l, i-1);
        quicksort(a, i+1, r);
    }

    //  partitioning element v (arbitrary choose a[r])
    //  left <= v, right >= v
    //  l..i (left partition),  i..j (unprocess), j..r (right partition)

    static int partition(double[] a, int l , int r){
        int i = l-1;
        int j = r;
        double v = a[r];
        for( ;; ){
            do{ i++; } while (a[i] < v);
            do{ j--; } while ((v < a[j]) && (j != l));
            if( i >= j) break;
            exch(a, i, j);
        }
        exch(a, i, r);
        return i;
    }

    //median-of-three partitioning
    //take sample from three elements, use the median of the three
    //sample left, middle, right

    static void quicksort2(double[] a, int l, int r){
        if (r <= l) return;
        exch(a, (l+r)/2, r-1);
        compExch(a, l, r-1);
        compExch(a, l, r);
        compExch(a, r-1, r);
        int i = partition(a, l+1, r-1);
        quicksort(a, l, i-1);
        quicksort(a, i+1, r);
    }
    public static void main (String[] args){
        for(int i = 0; i < N; i++)
            a[i] = Math.random();
        quicksort2(a, 0, N-1);
        if( N < 100 )
            for(int i = 0; i < N; i++)
                System.out.println(a[i] + " ");
        System.out.println("Compares used: " + cnt);
    }
}