import java.util.Scanner;

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

    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"
                + "Shell Sort\n"
                + "==========\n");

        setTraceLevel();

        // create an array of random integers
        int[] numbers = Common.randomNumbers(HOW_MANY, MAX / 10, MAX);
        Common.printArray(numbers);
        Common.pause();

        // sort it
        shellSort(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-sorted)\n"
                + "  2 - middle loop, too (inserted)\n"
                + "  3 - innermost loop (inserting)\n\n"
                + "Trace level: ";

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

    /**
     * Perform insertion sort on the given array.
     *
     * @param arr the array to sort
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        while (gap >= 1) {
            if (gap % 2 == 0) {
                ++gap;
            }
            if (traceLevel > 1) {
                System.out.println("..." + gap + "-sorting...");
                Common.printArray(arr);
                Common.pause();
            }
            for (int i = 0; i < arr.length - gap; ++i) {
                int p = i + gap;
                int temp = arr[p];
                if (traceLevel > 2) {
                    System.out.println("...inserting " + temp + "...");
                    Common.printOffset(arr, gap, i % gap);
                    Common.pause();
                }
                while (p >= gap && arr[p - gap] > temp) {
                    arr[p] = arr[p - gap];
                    p -= gap;
                    if (traceLevel > 2) {
                        System.out.println("...inserting " + temp + "...");
                        System.out.println("...copy up " + arr[p] + "...");
                        Common.printOffset(arr, gap, i % gap);
                        Common.pause();
                    }
                }
                arr[p] = temp;
                if (traceLevel > 1) {
                    System.out.println("one more inserted: ");
                    Common.printOffset(arr, gap, i % gap);
                    Common.pause();
                }
            }
            if (traceLevel > 0) {
                System.out.println("now " + gap + "-sorted");
                for (int rem = 0; rem < gap; ++rem) {
                    System.out.println("...offset " + rem);
                    Common.printOffset(arr, gap, rem);
                }
                Common.pause();
            }
            gap /= 2;
        }
    }

}