/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package insertionsort;

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

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
           int[] Array;
           int N;
 for (N = 1; 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];

//       for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
//        System.out.println();
        Bcnt.clr(); //counts comparisons while sorting of both arrays
        Bcnt2.clr(); //counts shifts while sorting of both arrays
        System.out.println("********* " + N + " *********");
        System.out.println("Sorting Array[" + N + "]");
        int invA = InversionCounter.Go(Array);
        System.out.println("Array had = " + invA + " inversions");
        insertionSort(Array);
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        int compA = Bcnt.get();
        System.out.print("comps(" + N +")");
        Bcnt.out(" = ");
        System.out.println();
        int shiftA = Bcnt.get();
        System.out.print("shifts(" + N +")");
        Bcnt2.outln(" = ");
        System.out.println("comps(" + N +") - inversions(" + N + ") = " + (compA - invA));
        System.out.println("N - Math.log(N)- 0.577216 = " + (N - Math.log(N)- 0.577216));
        Bcnt.clr(); //counts comparisons while sorting of both arrays
        Bcnt2.clr(); //counts shifts while sorting of both arrays

        System.out.println("Sorting ReversedArray[" + N + "]");
        int invB = InversionCounter.Go(ReversedArray);
        System.out.println("ReversedArray had = " + invB + " inversions");
        insertionSort(ReversedArray);
        for (int i = 0; i < N; i++) System.out.print(ReversedArray[i] + " ");
        System.out.println();
//        System.out.print("accumulated comps(" + N +")");
        int compB = Bcnt.get();
        System.out.print("comps(" + N +")");
        Bcnt.out(" = ");
        System.out.println();
        int shiftB = Bcnt.get();
//        System.out.print("accumulated shifts(" + N +")");
        System.out.print("shifts(" + N +")");
        Bcnt2.outln(" = ");
        System.out.println("comps(" + N +") - inversions(" + N + ") = " + (compB - invB));
        System.out.println("  " + (N*(N-1)/2) + " = N*(N-1)/2");
        System.out.println("  " + ((N+2)*(N-1)/2) + " = (N+2)*(N-1)/2");
        System.out.println("  " + (N*(N-1)/4) + " = N*(N-1)/4");
        System.out.println("Comparisons in both: " + (compA + compB));
        System.out.println("Theoretic average number of comps over all arrays of size " + N
                + " for InsertionSort = " + ((N-1)*N/4 + N - ((Math.log(N) + 0.577216 + 0.5/N))));

        System.out.println("2 * Theoretic average number of comps over all arrays of size " + N
                + " for InsertionSort = " + 2*((N-1)*N/4 + N - ((Math.log(N) + 0.577216 + 0.5/N))));

 }
}

    public static void  insertionSort(int[] E)
    {
        int n = E.length;
        if (n < 2) return;
        for (int i = 1; i < n; i++)
        {
            int x = E[i];
            E[shiftVacant(E, i, x)] = x;
        }
    }


   private static int shiftVacant(int[] E, int vacant, int x)
{
	while ((vacant > 0) && ((E[vacant - 1] > x) & Bcnt.incr()))
	{
		E[vacant] = E[vacant - 1];
                Bcnt2.incr();
		vacant --;
	}
	return vacant;
}


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

}