import java.util.Scanner;

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

    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"
                + "Bubble Sort\n"
                + "===========\n\n"
                + "This program counts how many operations it takes "
                + "for bubble sort to sort a\nreversed array "
                + "of various sizes, "
                + "and compares that result to the expected value\n"
                + "of 2N^2 - 2N.");

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

                // sort it
                int result = bubbleSort(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 bubble sort on the given array.
     *
     * @param arr the array to sort
     * @return the number of array operations (comparisons and assignments)
     */
    public static int bubbleSort(int[] arr) {
        int count = 0;
        for (int i = arr.length - 1; i > 0; --i) {
            for (int j = 0; j < i; ++j) {
                ++count;
                if (arr[j] > arr[j + 1]) {
                    count += swap(arr, j, j + 1);
                }
            }
        }
        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 bubble sort in the worst
     * case.
     *
     * @param len the length of the list
     * @return the expected number of operations for bubble-sorting a list of
     * the given length
     */
    private static int expected(int len) {
        return 2 * (len * len - len);
    }

    /**
     * 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();
    }

}