import java.util.Scanner;

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

    public static final Scanner KBD = Common.KBD;
    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");
        
        System.out.println("This program demonstrates an improvement "
                + "to bubble sort.\n");

        // demo
        int[] numbers = {3, 4, 5, 1, 2, 6, 7, 8, 9, 10};
        System.out.println("A mostly sorted list:");
        Common.printArray(numbers);
        Common.pause();
        traceLevel = 1;
        bubbleSort(numbers);
        System.out.println("The sorted array:");
        Common.printArray(numbers);
        Common.pause();
        System.out.println("An entirely sorted array:");
        Common.printArray(numbers);
        bubbleSort(numbers);
        System.out.println("The sorted array:");
        Common.printArray(numbers);
        Common.pause();
        
        // now for a longer version
        System.out.println("Now to try a random list.\n");
        setTraceLevel();
        
        // create an array of random integers
        numbers = Common.randomNumbers(HOW_MANY, MAX / 10, MAX);
        Common.printArray(numbers);
        Common.pause();

        // sort it
        bubbleSort(numbers);
        
        // show it sorted
        System.out.println("Array now sorted");
        Common.printArray(numbers);
        Common.pause();
    }

    /**
     * Prompt for and read a level of tracing to do.
     */
    public static void setTraceLevel() {
        String traceMenu = "Enter a trace level: \n"
                + "  0 - no tracing\n"
                + "  1 - outer loop only\n"
                + "  2 - inner loop as well\n\n"
                + "Trace level: ";

        System.out.print(traceMenu);
        traceLevel = KBD.nextInt();
        KBD.nextLine();
        while (traceLevel < 0 || 2 < traceLevel) {
            System.out.print(traceMenu);
            traceLevel = KBD.nextInt();
            KBD.nextLine();
        }
    }

    /**
     * Perform bubble sort on the given array.
     *
     * @param arr the array to sort
     */
    public static void bubbleSort(int[] arr) {
        String msg;
        for (int i = arr.length - 1; i > 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (traceLevel > 1) {
                    Common.printArray(arr, j, j + 2);
                }
                if (arr[j] > arr[j + 1]) {
                    msg = "swap";
                    Common.swap(arr, j, j + 1);
                } else {
                    msg = "ok";
                }
                if (traceLevel > 1) {
                    System.out.println("...." + msg + "....");
                    Common.pause();
                }
            }
            if (traceLevel > 0) {
                System.out.println("Unsorted part");
                Common.printArray(arr, 0, i);
                System.out.println("Sorted part");
                Common.printArray(arr, i, arr.length);
                Common.pause();
            }
        }
    }

}