import java.util.*;

public class Main {

    final static int ARRAY_LENGTH = 1000;
    final static int RANDOM_RANGE = 1000;
    final static int OPT_CUTOFF = 10;
    final static int RUN_TIMES = 10;

    public static void main(String[] args) {
        long startTime = 0, endTime = 0, totalTime = 0;
        Integer[] array = new Integer[ARRAY_LENGTH];

        //efficiency run for QuickSort
        for (int i = 0; i < RUN_TIMES; i++) {
            //populate an array with 1000 random Integer
            array = createArray(ARRAY_LENGTH);
            startTime = System.nanoTime();
            //QuickSort
            //Note: I did not use Arrays.sort() for this function because it is
            //a "tuned" quicksort according to the Java api specifications.
            //I thought the optimization might skew the results of this project.
            quickSort(array, 0, array.length - 1);
            endTime = System.nanoTime();
            totalTime = totalTime + (endTime - startTime);
        }
        // for(int i = 1; i < array.length; i++)
        //   System.out.println(array[i]);
        System.out.println("<<quickSort>>\nMean running time for "
                + RUN_TIMES + " runs: " + totalTime / RUN_TIMES);

        totalTime = 0;

        //efficiency run for OptQSort1
        for (int i = 0; i < RUN_TIMES; i++) {
            //populate an array with 1000 random Integer
            array = createArray(ARRAY_LENGTH);
            startTime = System.nanoTime();
            //optimized quickSort1
            OptQSort1(array, 0, array.length - 1);
            endTime = System.nanoTime();
            totalTime = totalTime + (endTime - startTime);
        }
        //for(int i = 1; i < array.length; i++)
        // System.out.println(array[i]);
        System.out.println("<<OptQSort1>>\nMean running time for "
                + RUN_TIMES + " runs: " + totalTime / RUN_TIMES);

        totalTime = 0;

        //efficiency run for OptQSort2
        for (int i = 0; i < RUN_TIMES; i++) {
            //populate an array with 1000 random Integer
            array = createArray(ARRAY_LENGTH);
            startTime = System.nanoTime();
            //optimized quickSort2
            OptQSort2(array, 0, array.length - 1);
            endTime = System.nanoTime();
            totalTime = totalTime + (endTime - startTime);
        }
        //for(int i = 1; i < array.length; i++)
        // System.out.println(array[i]);
        System.out.println("<<OptQSort2>>\nMean running time for "
                + RUN_TIMES + " runs: " + totalTime / RUN_TIMES);
    }

    //this method creates an array of random integers of a specified size
    public static Integer[] createArray(int arraySize) {
        Integer[] array = new Integer[arraySize];
        Random rand = new Random();

        //populate array with random integers.
        for (int i = 0; i < arraySize; i++) {
            array[i] = rand.nextInt(RANDOM_RANGE);
            //array[i] = i;
        }

        return array;
    }

    //this method uses a quick sort algorithm to sort an array.
    public static void quickSort(Integer[] array, int first, int last) {
        if (last > first) {
            //create partitions
            Integer pivotIndex = partition(array, first, last);
            quickSort(array, first, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, last);
        }
    }

    //This method finds the partitions for the quicksort methods.
    private static int partition(Integer[] array, int first, int last) {

        Integer pivot = array[first];
        int low = first + 1;
        int high = last;

        while (high > low) {
            while (low <= high && array[low] <= pivot) {
                low++;
            }
            while (low <= high && array[high] > pivot) {
                high--;
            }

            if (high > low) {
                int temp = array[high];
                array[high] = array[low];
                array[low] = temp;
            }
        }
        while (high > first && array[high] >= pivot) {
            high--;
        }

        if (pivot > array[high]) {
            array[first] = array[high];
            array[high] = pivot;
            return high;
        } else {
            return first;
        }
    }

    //this method uses an optimized quick sort algorithm to sort an array.
    public static void OptQSort1(Integer[] array, int first, int last) {
        //create partitions
        Integer pivotIndex = partition(array, first, last);
        if (last - first > OPT_CUTOFF) {
            quickSort(array, first, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, last);
        }
            insertionSort(array, first, pivotIndex - 1);
            insertionSort(array, pivotIndex + 1, last);

    }

    //this method uses an optimized quick sort algorithm to sort an array.
    public static void OptQSort2(Integer[] array, int first, int last) {
        if (last - first > OPT_CUTOFF) {
            //create partitions
            Integer pivotIndex = partition(array, first, last);
            quickSort(array, first, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, last);
        }
            //insertion sort
            insertionSort(array, 0, array.length);
    }

    //this method performs an insertion sort on the partially ordered arrays
    //from the quicksort methods.
    public static void insertionSort(Integer[] array, int first, int last) {
        for (int i = first + 1; i < last; i++) {
            Integer currentElement = array[i];
            int k;
            for (k = i; k > 0 && array[k - 1] > currentElement; k--) {
                array[k] = array[k - 1];
            }
            array[k] = currentElement;
        }
    }
}