import java.util.Arrays;

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

    /**
     * Sort the given array using the quicksort algorithm.
     *
     * @param arr the array to sort
     */
    public static void sort(int[] arr) {
        sortIntoRange(arr, 0, arr.length, 0, arr.length);
    }

    /**
     * Partially sort the given array using the quicksort algorithm so that the
     * given range contains its proper values. Everything below the range will
     * be less than or equal to the smallest value in the sorted range, and
     * everything above the range will be greater than or equal to the largest
     * value in the sorted range. Elements in the range will be sorted.
     *
     * @param arr the array to (partially) sort
     * @param sortBegin the lower bound (inclusive) of the part being sorted
     * @param sortEnd the upper bound (exclusive) of the part being sorted
     */
    public static void sortIntoRange(int[] arr, int sortBegin, int sortEnd) {
        sortIntoRange(arr, 0, arr.length, sortBegin, sortEnd);
    }

    /**
     * Sort the given part of the given array using the quicksort algorithm. The
     * values outside the range are ignored. Values in the range will be sorted.
     *
     * @param arr the array to (partially) sort
     * @param sortBegin the lower bound (inclusive) of the part being sorted
     * @param sortEnd the upper bound (exclusive) of the part being sorted
     */
    public static void sortPart(int[] arr, int sortBegin, int sortEnd) {
        sortIntoRange(arr, sortBegin, sortEnd, sortBegin, sortEnd);
    }

    /**
     * Partially sort the given array using the quicksort algorithm so that the
     * lowest part contains its proper values. The first {@code numToGet}
     * elements will be sorted. Everything above that in the array will be
     * greater than or equal to the largest value in the sorted range.
     *
     * @param arr the array to (partially) sort
     * @param numToGet how many of the lowest elements to get
     */
    public static void sortSmallest(int numToGet, int[] arr) {
        sortIntoRange(arr, 0, arr.length, 0, numToGet);
    }

    /**
     * Partially sort the given array using the quicksort algorithm so that the
     * highest part contains its proper values. The last {@code numToGet}
     * elements will be sorted. Everything below that in the array will be less
     * than or equal to the smallest value in the sorted range.
     *
     * @param arr the array to (partially) sort
     * @param numToGet how many of the lowest elements to get
     */
    public static void sortLargest(int numToGet, int[] arr) {
        sortIntoRange(arr, 0, arr.length, arr.length - numToGet, arr.length);
    }

    /**
     * Partially sort the given array using the quicksort algorithm so that the
     * middle part contains its proper values. The middle part will be <em>at
     * least</em> {@code numToGet} elements long. (It will be increased by one
     * if necessary to make the lower and higher parts of the array the same
     * length.) The middle part will be sorted. Everything below the range will
     * be less than or equal to the smallest value in the sorted range, and
     * everything above the range will be greater than or equal to the largest
     * value in the sorted range.
     *
     * @param arr the array to (partially) sort
     * @param numToGet how many of the lowest elements to get
     */
    public static void sortMiddle(int numToGet, int[] arr) {
        int numOutside = arr.length - numToGet;
        int numBelow = numOutside / 2;
        sortIntoRange(arr, 0, arr.length, numBelow, arr.length - numBelow);
    }

    /*
     * ---------- Implementation ----------
     */
    /**
     * A modified version of quicksort that only sorts part of the array.
     *
     * @param arr the array to (partially) sort
     * @param sortBegin the lower bound (inclusive) of the part being sorted
     * @param sortEnd the upper bound (exclusive) of the part being sorted
     * @param reqBegin the lower bound (inclusive) of the part needing to be
     * sorted
     * @param reqEnd the upper bound (exclusive) of the part needing to be
     * sorted
     */
    private static void sortIntoRange(
            int[] arr,
            int sortBegin,
            int sortEnd,
            int reqBegin,
            int reqEnd) {
        // only need to sort subsections of length 2 or more
        // also only need to sort parts that overlap the part needing sorted
        if (sortEnd - sortBegin > 1
                && reqBegin < sortEnd && sortBegin < reqEnd) {
            // pick pivot
            int pivot = pickAndMovePivot(arr, sortBegin, sortEnd);

            // partition
            int pivotPlace = partition(arr, sortBegin, sortEnd, pivot);

            // quickSelect lower part (for sortSmallest values)
            sortIntoRange(arr, sortBegin, pivotPlace, reqBegin, reqEnd);

            // quickSelect upper part
            sortIntoRange(arr, pivotPlace + 1, sortEnd, reqBegin, reqEnd);
        }
    }

    /**
     * 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 sortMiddle
        while (true) {
            if (arr[lowerEdge] < pivot) {
                // near-front-small
                lowerEdge++;
            } else if (lowerEdge >= upperEdge) {
                // crossed in the sortMiddle
                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;
    }

}