/**
 * SorterForTest.java
 * Jeff Ondich, 2 Feb 2005
 * Modified 5 March 2019
 * 
 * For use in a takehome exam.
 */

public class SorterForTest {
    /**
     * Generates a pseudo-random permutation of the integers from 0 to a.length - 1.
     * See p. 139 of "Seminumerical Algorithms, 2nd edition," by Donald Knuth.
     */
    public static void fillAndShuffle(int[] a) {
        // Fill the array with the integers from 0 to a.length - 1.
        int k;
        for (k = 0; k < a.length; k++) {
            a[k] = k;
        }

        // Shuffle.
        for (k = a.length - 1; k > 0; k--) {
            int swapIndex = (int)Math.floor(Math.random() * (k + 1));
            int temp = a[k];
            a[k] = a[swapIndex];
            a[swapIndex] = temp;
        }
    }

    /**
     * Prints the elements of the specified array, separated by spaces,
     * to standard output.
     */
    public static void printArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }

    /**
     * Sorts the specified array in increasing order.
     */
    public static void insertionSort(int[] a) {
        for (int j = 1; j < a.length; j++) {
            int itemToInsert = a[j];
            int k;
            for (k = j - 1; k >= 0 && itemToInsert < a[k]; k--) {
                a[k + 1] = a[k];
            }
            a[k + 1] = itemToInsert;
        }
    }

    /**
     * Sorts the specified array in increasing order.
     */
    public static void selectionSort(int[] a) {
        for (int j = 0; j < a.length - 1; j++) {
            int indexOfMinimum = j;
            for (int k = j + 1; k < a.length; k++) {
                if (a[k] < a[indexOfMinimum]) {
                    indexOfMinimum = k;
                }
            }

            int temp = a[indexOfMinimum];
            a[indexOfMinimum] = a[j];
            a[j] = temp;
        }
    }

    /**
     * Sorts the specified array in increasing order.
     */
    public static void quickSort(int[] a) {
        quickSortRange(a, 0, a.length - 1);
    }

    private static void quickSortRange(int[] a, int first, int last) {
        if (first < last) {
            int left = first + 1;
            int right = last;
            int pivotValue = a[first];
            while (left <= right) {
                while (left <= right && a[left] <= pivotValue) {
                    left++;
                }

                while (left <= right && pivotValue < a[right]) {
                    right--;
                }

                if (left <= right) {
                    int save = a[left];
                    a[left] = a[right];
                    a[right] = save;
                }
            }

            a[first] = a[right];
            a[right] = pivotValue;
            quickSortRange(a, first, right - 1);
            quickSortRange(a, left, last);
        }
    }

    /**
     * Sorts the specified array in increasing order.
     */
    public static void mergeSort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        int [] tempArray = new int[a.length];
        mergeSortRange(a, tempArray, 0, a.length - 1);
    }

    /**
     * The recursive method that implements the mergesort algorithm.
     */
    private static void mergeSortRange(int[] a, int[] tempArray, int bottom, int top) {
        if (bottom < top) {
            int middle = (bottom + top) / 2;
            mergeSortRange(a, tempArray, bottom, middle);
            mergeSortRange(a, tempArray, middle + 1, top);
            merge(a, tempArray, bottom, middle, top);
        }
    }

    /**
     * Merges two adjacent portions of a given array.
     */
    private static void merge(int[] a, int[] tempArray, int bottom, int middle, int top) {
        int i = bottom;
        int j = middle + 1;
        int k = 0;

        while (i <= middle && j <= top) {
            if (a[i] < a[j]) {
                tempArray[k] = a[i];
                i++;
            } else {
                tempArray[k] = a[j];
                j++;
            }
            k++;
        }
    
        if (i > middle) {
            while (j <= top) {
                tempArray[k] = a[j];
                j++;
                k++;
            }
        } else {
            while (i <= middle) {
                tempArray[k] = a[i];
                i++;
                k++;
            }
        }

        for (i = bottom; i <= top; i++) {
            a[i] = tempArray[i - bottom];
        }
    }

    public static void main(String[] args) {
        int[] numbers = new int[20];
        fillAndShuffle(numbers);
        quickSort(numbers);
        printArray(numbers);
    }
}