/**
 * A program to select the N smallest values in an array of randomly generated
 * numbers.
 *
 * @author Mark Young (A00000000)
 */
import java.util.Scanner;

public class QuickSort {

    /**
     * biggest number in list
     */
    private static final int BIGGEST = 1000;

    /**
     * keyboard scanner for whole program
     */
    private static final Scanner KBD = new Scanner(System.in);

    public static void main(String[] args) {
        // introduce program
        System.out.print("\n\n"
                + "QuickSort\n"
                + "---------\n\n"
                + "This program demonstrates the QuickSort algorithm.\n\n"
                + "By Mark Young (A00000000).\n\n");

        // create list
        System.out.print("How long should I make the list? ");
        int numElts = KBD.nextInt();
        KBD.nextLine();
        int[] arr = new int[numElts];
        for (int i = 0; i < numElts; i++) {
            arr[i] = (int) (BIGGEST * Math.random());
        }

        // show the original array
        System.out.println("\nArray values before sorting:");
        PrintTrace.printArray(arr);
        pause();

        // sort the array
        quickSort(arr, 0, arr.length);

        // show the sorted array
        System.out.println("\nThe sorted array:");
        PrintTrace.printArray(arr);
        pause();

        // do a test to make sure that the list is sorted
        if (!sorted(arr)) {
            System.err.println("Oops!  That didn't work!");
        }
    }

    /**
     * Sort an array using the quicksort algorithm. Report what parts of the
     * array are being sorted.
     *
     * @param arr the array to (partially) sort
     * @param begin the lower bound (inclusive) of the part being sorted
     * @param end the upper bound (exclusive) of the part being sorted
     */
    public static void quickSort(
            int[] arr,
            int begin,
            int end) {
        // only need to sort subsections of length 2 or more
        if (end - begin > 1) {
            // report the range that's being sorted
            System.out.println("Sorting from " + begin + " to " + end + "...");

            // pick pivot
            int pivot = pickAndMovePivot(arr, begin, end);

            // partition
            int pivotPlace = partition(arr, begin, end, pivot);
            System.out.printf("After partitioning at %d (pivot = %d):%n",
                    pivotPlace, pivot);
            PrintTrace.printArray(arr, begin, end);
            pause();

            // quickSort lower part (for smallest values)
            quickSort(arr, begin, pivotPlace);

            // quickSort upper part
            quickSort(arr, pivotPlace + 1, end);
        }
    }

    /**
     * Use the median-of-three method to pick a pivot value, then move it to the
     * end of the array.
     *
     * @param arr the array to pick the pivot from
     * @param begin the lower bound (inclusive) of the part of the array being
     * sorted
     * @param end the upper bound (exclusive) of the part of the array being
     * sorted
     * @return the value chosen as the pivot
     */
    private static int pickAndMovePivot(int[] arr, int begin, int end) {
        int p1 = begin;
        int p2 = end - 1;
        int p3 = begin + (end - begin) / 2;
        if (arr[p1] < arr[p2]) {
            if (arr[p2] < arr[p3]) {
                return movePivot(arr, p2, end);
            } else if (arr[p1] < arr[p3]) {
                return movePivot(arr, p3, end);
            } else {
                return movePivot(arr, p1, end);
            }
        } else if (arr[p1] < arr[p3]) {
            return movePivot(arr, p1, end);
        } else if (arr[p2] < arr[p3]) {
            return movePivot(arr, p3, end);
        } else {
            return movePivot(arr, p2, end);
        }
    }

    /**
     * Move the pivot value to the end of the part of the array being sorted.
     *
     * @param arr the array being sorted
     * @param pivotStart the index where the pivot value was in the array
     * @param end the upper bound (exclusive) of the part of the array being
     * sorted
     * @return the value moved to the end (i.e. the pivot value)
     */
    private static int movePivot(int[] arr, int pivotStart, int end) {
        swap(arr, pivotStart, end - 1);
        return arr[end - 1];
    }

    /**
     * Partition the part of the array being sorted. That is, move all the
     * smaller values toward the front of the array and the bigger ones toward
     * the back. Bigger and smaller are determined with respect to the pivot
     * value.
     *
     * @param arr the array being sorted
     * @param begin the lower bound (inclusive) of the part of the array being
     * sorted
     * @param end the upper bound (exclusive) of the part of the array being
     * sorted
     * @param pivot the pivot value
     * @return the position the pivot value ended up in
     */
    private static int partition(int[] arr, int begin, int end, int pivot) {
        int lowerEdge = begin;
        int upperEdge = end - 2;   // pivot is in end-1

        // swap near-front-larger and near-back-smaller values until we cross
        // in the middle
        while (true) {
            if (arr[lowerEdge] < pivot) {
                // near-front-small
                lowerEdge++;
            } else if (lowerEdge >= upperEdge) {
                // crossed in the middle
                break;
            } else if (pivot < arr[upperEdge]) {
                // near-back-large
                upperEdge--;
            } else {
                // near-front-large and near-back-small
                swap(arr, lowerEdge, upperEdge);
                lowerEdge++;
                upperEdge--;
            }
        }

        // move the pivot, if necessary
        if (pivot < arr[lowerEdge]) {
            swap(arr, lowerEdge, end - 1);
        }

        // return the location of the/a pivot value
        return lowerEdge;
    }

    private static void swap(int[] arr, int p1, int p2) {
        int temp = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = temp;
    }

    /**
     * Wait for the user to press the enter key.
     */
    public static void pause() {
        System.out.print("\n...Press ENTER...");
        KBD.nextLine();
        System.out.println();
    }

    /**
     * Check whether the given array is sorted.
     *
     * @param arr the array to check
     * @return true if arr is sorted; false otherwise
     */
    private static boolean sorted(int[] arr) {
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i - 1] > arr[i]) {
                return false;
            }
        }
        return true;
    }

}