import java.util.Scanner;

/**
 *
 * @author Mark Young (A00000000)
 */
public class InsertionSort {

    private static final Scanner KBD = new Scanner(System.in);
    private static final int HOW_MANY = 10;
    private static final int MAX = 1000;
    private static int traceLevel = 0;

    public static void main(String[] args) {
        System.out.println("\n\n"
                + "Insertion Sort\n"
                + "==============\n\n"
                + "This program counts how many operations it takes "
                + "for insertion sort to sort a\nreversed array "
                + "of various sizes, "
                + "and compares that result to the expected value\n"
                + "of N^2 + N - 2.");

        int len = 0;
        do {
            System.out.println();
            System.out.printf("%10s %10s %10s%n", 
                    "Length", "Operations", "Expected");
            for (int i = 1; i <= HOW_MANY; ++i) {
                // create an array of random integers
                ++len;
                int[] numbers = makeReversedArray(len);

                // sort it
                int result = insertionSort(numbers);

                // report operation count
                System.out.printf("%10d %10d %10d%n", 
                        len, result, expected(len));
            }
        } while (userContinue());
        
    }

    /**
     * Make an array of the given length, with the numbers 1 .. {@code length}
     * in reverse order. This is the worst case for sorting for many methods.
     *
     * @param length the length of the array to create
     * @return an array containing the numbers from {@code length} down to 1
     */
    private static int[] makeReversedArray(int length) {
        int[] result = new int[length];
        for (int i = 0; i < length; ++i) {
            result[i] = length - i;
        }
        return result;
    }

    /**
     * Perform insertion sort on the given array.
     *
     * @param arr the array to sort
     * @return the number of array operations (comparisons and assignments)
     */
    public static int insertionSort(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length - 1; ++i) {
            int p = i + 1;
            ++count;
            int temp = arr[p];
            while (p > 0 && (++count > 0) && arr[p - 1] > temp) {
                ++count;
                arr[p] = arr[p - 1];
                --p;
            }
            ++count;
            arr[p] = temp;
        }
        return count;
    }

    /**
     * Swap two array elements
     *
     * @param arr the array to swap elements of
     * @param one one index to swap to/from
     * @param other other index to swap to/from
     * @return the number of array operations (assignments)
     */
    private static int swap(int[] arr, int one, int other) {
        if (one != other) {
            int temp = arr[one];
            arr[one] = arr[other];
            arr[other] = temp;
            return 3;   // three assignments
        } else {
            return 0;
        }
    }

    /**
     * Calcuilate how many operations we'd expect for insertion sort in the worst
     * case.
     *
     * @param len the length of the list
     * @return the expected number of operations for insertion-sorting a list of
     * the given length
     */
    private static int expected(int len) {
        return len * len + len - 2;
    }

    /**
     * Ask the user if they'd like to continue.
     *
     * @return true if the user wants to continue; false otherwise
     */
    private static boolean userContinue() {
        System.out.print("\nPress ENTER to continue or N or Q to quit: ");
        return KBD.nextLine().isEmpty();
    }

}