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

package inversions;

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

   /**
     * @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++)
 {
        System.out.println("********* " + 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();
        cnt.clr(); //counts comparisons while sorting of both arrays
        cnt2.clr(); //counts shifts while sorting of both arrays
        System.out.println("Sorting Array[" + N + "]");
        Go(Array);
//        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();
        System.out.print("shifts(" + N +")");
        cnt2.out(" = ");
        System.out.println("  " + (N*(N-1)/4) + " = N*(N-1)/4");

//        cnt.clr(); //counts comparisons while sorting of both arrays
//        cnt2.clr(); //counts shifts while sorting of both arrays

        System.out.println("Sorting ReversedArray[" + N + "]");
        Go(ReversedArray);
//        for (int i = 0; i < N; i++) System.out.print(ReversedArray[i] + " ");
//        System.out.println();
        System.out.print("accumulated comps(" + N +")");
        cnt.out(" = ");
        System.out.println();
        System.out.print("accumulated shifts(" + N +")");
        cnt2.out(" = ");
        System.out.println("  " + (N*(N-1)/2) + " = N*(N-1)/2");

        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  Go(int[] A)
    {
        int n = A.length;
        if (n < 2) return;
        for (int i = 1; i < n; i++)
        {
            int j = 0;
            while ((j < i) && Comp(A[j] , A[i])) j++;
            if (j < i)
            {                
                int x = A[i];
                for (int k = i; k > j; k--)
                {
                    A[k] = A[k - 1];
                    cnt2.incr();
                }
                A[j] = x;
            }

        }

    }

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

}