/**
 * 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 QuickSelect {

    /**
     * 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"
                + "QuickSelect\n"
                + "-----------\n\n"
                + "This program demonstrates using the QuickSort algorithm "
                + "to find the smallest\nelements of a list.\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());
        }

        // get how many small values we want
        System.out.print("How many of the smallest elements do you want? ");
        int numToGet = KBD.nextInt();
        KBD.nextLine();

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

        // select the smallest elements
        quickSelect(arr, 0, arr.length, numToGet);

        // show the smallest elements
        System.out.println("\nThe " + numToGet + " smallest elements:");
        PrintTrace.printArray(arr, 0, numToGet);
        pause();

        // show the remaining elements
        System.out.println("\nThe remaining elements:");
        PrintTrace.printArray(arr, numToGet, arr.length);
        pause();

        // do a test to make sure that the chosen elements ARE the smallest
        if (max(arr, 0, numToGet) > min(arr, numToGet, arr.length)) {
            System.err.println("Oops!  That didn't work!");
        }
    }

    /**
     * A modified version of quicksort that only sorts the lower end of the
     * array. It reports its actions as it goes along.
     *
     * @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
     * @param numToGet the upper bound (exclusive) of the part needing to be
     * sorted
     */
    public static void quickSelect(
            int[] arr,
            int begin,
            int end,
            int numToGet) {
        // only need to sort subsections of length 2 or more
        if (end - begin > 1) {
            // we don't need to sort if there are numToGet elements BELOW begin
            if (numToGet <= begin) {
                System.out.printf("We can skip sorting from %d to %d.%n",
                        begin, end);
                return;
            }

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

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

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

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

    /**
     * Find the maximum value in part of the array.
     * 
     * @param arr the array to search
     * @param begin the lower bound (inclusive) of the part to search
     * @param end the upper bound (exclusive) of the part to search
     * @return the maximum value in the given part of the array
     */
    private static int max(int[] arr, int begin, int end) {
        int max = Integer.MIN_VALUE;
        for (int i = begin; i < end; ++i) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    /**
     * Find the minimum value in part of the array.
     * 
     * @param arr the array to search
     * @param begin the lower bound (inclusive) of the part to search
     * @param end the upper bound (exclusive) of the part to search
     * @return the minimum value in the given part of the array
     */
    private static int min(int[] arr, int begin, int end) {
        int min = Integer.MAX_VALUE;
        for (int i = begin; i < end; ++i) {
            min = Math.min(min, arr[i]);
        }
        return min;
    }

}