import java.util.*;
import java.lang.*;

/**
 * Class for QuickSort Investigation, exploring how changing 
 * the switch to insertion sort affects runtime. Note that 
 * there are many private methods here for how quicksort works.
 * (You won't need to consider all of them, especially fillAndShuffle().)
 * You'll modify main, and you're welcome to add any additional
 * methods you'd like. You will likely need to modify the way in which
 * the insertionSort threshold (currently set with MIN_SIZE) is
 * specified.
 * 
 * @author Anna Rafferty
 * @author Layla Oesper
 * @author Eric Alexander
 * @author Titus Klinge
 * @author [YOUR NAMES HERE]
 */
public class QuickSort
{
    private static final int MIN_SIZE = 10;

    /**
     * Sorts an array in increasing order using quicksort.
     * 
     * @param arr the array to be sorted
     */
    public static void quickSort(int[] arr)
    {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * Recursive helper method to quicksort.
     *
     * @param arr the array to be sorted
     * @param firstI the first index to be considered
     * @param lastI the last index to be considered
     */
    private static void quickSort(int[] arr, int firstI, int lastI)
    {
        if (lastI - firstI <= MIN_SIZE)
        {
            insertionSort(arr, firstI, lastI);
        } else
        {
            int pivotI = partition(arr, firstI, lastI);
            quickSort(arr, firstI, pivotI - 1);
            quickSort(arr, pivotI + 1, lastI);
        }
    }

    /**
     * Partitions slice of given array between two given indices around a pivot.
     *
     * @param arr the array to be partitioned
     * @param firstI the first index to be considered in partitioning
     * @param lastI the last index to be considered in partitioning
     */
    private static int partition(int[] arr, int firstI, int lastI)
    {
        // Select middle item as pivot
        int pivotI = (lastI + firstI) / 2;
        int pivotV = arr[pivotI];
        swap(arr, firstI, pivotI);

        // March up and down closer and closer until they cross,
        // swapping values that are out of place
        int up = firstI + 1;
        int down = lastI;
        boolean done = false;
        while (!done)
        {
            // March up to find value greater than pivotV
            while (up < lastI && arr[up] < pivotV)
            {
                up++;
            }
            // March down to find value less than pivotV
            while (down > firstI && arr[down] > pivotV)
            {
                down--;
            }

            // If up and down passed, we're done.
            // Else, swap their values and keep going.
            if (up < down)
            {
                swap(arr, up, down);
                up++;
                down--;
            } else
            {
                done = true;
                swap(arr, firstI, down);
            }
        }

        // down will be pointing to the index of the pivot
        return down;
    }
    
    /**
     * Sorts the specified array between given indices.
     *
     * @param arr the array to be sorted
     * @param firstI the first index to be considered
     * @param lastI the last index to be considered
     */
    private static void insertionSort(int[] arr, int firstI, int lastI)
    {
        for (int i = firstI + 1; i <= lastI; i++)
        {
            int numToInsert = arr[i];
            int j = i;
            while (j > firstI && arr[j-1] > numToInsert)
            {
                arr[j] = arr[j-1];
                j--;
            }
            arr[j] = numToInsert;
        }
    }

    /**
     * Helper method that swaps two values in a given array.
     *
     * @param arr the array containing the values
     * @param i the index of the first value
     * @param j the index of the second value
     */
    private static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * Helper function you may decide to use to print out a given array to the console.
     *
     * @param arr the array to print
     */
    private static void printArr(int[] arr)
    {
        StringJoiner sj = new StringJoiner(", ", "[", "]");
        for (int i = 0; i < arr.length; i++)
        {
            sj.add(Integer.toString(arr[i]));
        }
        System.out.println(sj.toString());
    }

    /**
     * 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;
        }
    }
    
    /**
     * You'll put your experiments for the investigation here. 
     * The current contents are just to give you an example.
     */
    public static void main(String[] args)
    {
        System.err.println("Investigation not yet designed and carried out!");
        
        //This is just an example of how you might do timing - you can erase
        // it and write your own investigation.
        int[] quicksortArray = new int[1000000];
        fillAndShuffle(quicksortArray);
        long startTime = System.currentTimeMillis();
        quickSort(quicksortArray);
        long endTime = System.currentTimeMillis();
        System.out.println("Array length: " + quicksortArray.length + "; time to sort (ms): " + (endTime-startTime));
        
    }   
}