//Copyright Dr. Marek A. Suchenek, 2010, 2011, 2012, 2013, 2014, 2015
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package inversions;

/**
 *
 * @author suchenek
 */
public class QuickSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
           int[] Array;
           int N;
 for (N = 2; N<=100; N++)
 {
        Array = new int[N];
        for (int i = 0; i < N; i++)
        Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
//        for (int i = 0; i < N; i++)
//        Array[i] = i;
       int[] ReversedArray = new int[N];
        for (int i = 0; i < N; i++)
        ReversedArray[i] = Array[N-i -1];
        System.out.println("*** " + N + "-element array to be sorted ***");

       for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        cnt.clr(); //counts comps while sorting of both arrays
        cnt2.clr(); //counts shifts while sorting of both arrays
        cnt3.clrAll(); //counts recursive calls while sorting of both arrays
                       //max value indicates the size of the largest depth of recursion
        System.out.println("Sorting Array[" + N + "]");
        Sort(Array, 0, N-1);
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        System.out.print("comps(" + N +")");
        cnt.out(" = ");
        System.out.println("  N*(N-1)/2 = " + N*(N-1)/2);
        System.out.print("shifts(" + N +")");
        cnt2.outln(" = ");
//        System.out.print("calls(" + N +")");
//        cnt3.out(" = ");
        System.out.println("The largest stack was " + cnt3.getMax());
//        cnt.clr(); //counts comparisons while sorting of both arrays
//        cnt2.clr(); //counts shifts while sorting of both arrays
        cnt3.clr();

        System.out.println("Sorting ReversedArray[" + N + "]");
        Sort(ReversedArray, 0, N-1);
        for (int i = 0; i < N; i++) System.out.print(ReversedArray[i] + " ");
        System.out.println();
        System.out.print("accumulated comps(" + N +")");
        cnt.outln(" = ");
//        System.out.println("  2*N*(N-1)/2 = " + 2*N*(N-1)/2);
        System.out.print("accumulated shifts(" + N +")");
        cnt2.outln(" = ");
//        System.out.print("accumulated calls(" + N +")");
//        cnt3.out(" = ");
        System.out.println("The largest stack was " + cnt3.getMax());

        System.out.println("2 * Theoretic average number of comps over all arrays of size " + N
                + " for QuickSort = " + 2*(1.386*(N+1)*(Math.log(N)/Math.log(2)) - 2.846*N + 2.154));

 }
}

    private static int Split(int[] L, int lo, int hi)
            //Uses the occupant x at index lo in array L as pivot,
            //sends all elements < x to the begining of the range (lo, hi), and
            //all elements >=x to the end of that range
{
    int splitPoint = lo;
    int x = L[splitPoint];
    for (int i = lo+1; i <= hi; i++)
    {
        if (Comp(L[i], x)) //need to move L[i] before split point
                {
            L[splitPoint] = L[i];
            cnt2.incr();
            splitPoint++;
            L[i] = L[splitPoint];
            cnt2.incr();
        }
    }
    L[splitPoint] = x;
    cnt2.incr();
    return splitPoint;
}

    public static void  Sort(int[] A, int lo, int hi)
    {
        cnt3.incr();
        if ((hi - lo) < 1)
        {
            cnt3.decr();
            return;
        }
        int splitPoint = Split(A, lo, hi);
        Sort(A, lo, splitPoint - 1);
        Sort(A, splitPoint + 1, hi);
        cnt3.decr();

    }

    public static Boolean Comp(int x, int y)
            //compares x to A[ind] and increments cnt
    {
        cnt.incr();
        return (x < y);
    }

}