import java.lang.System;
import java.lang.Math;

public class sortTest {
    // this procedure provides timing data for insertion sort and quicksort
  
    // variable to check correctness
    static boolean checkCorrectness = true;

    public static void insertionSort (int [] a) {
        // method to sort using the insertion sort
        for (int k = 1; k < a.length; k++) {
            int item = a[k];
            int i = k-1;
            while ((i >= 0) && a[i] > item){
                a[i+1] = a[i];
                i--;
            }
            a[i+1] = item;
        }

        if (checkCorrectness) {
            boolean ok = true;
            for (int k = 1; k < a.length&&ok; k++) {
                ok = a[k-1] <= a[k];
            }
            if (!ok) {
                SimpleOutput out = new SimpleOutput();
                out.println ("error:  insertion sort");
                for (int k = 0; k < a.length; k++) {
                    out.print("\t" + a[k]);
                }
                out.println();
            }
        }
        
    } // insertionSort

    public static void quicksort (int [] a) {
        // method to sort using the quicksort
        quicksortKernel (a, 0, a.length-1);

        if (checkCorrectness) {
            boolean ok = true;
            for (int k = 1; k < a.length&&ok; k++) {
                ok = a[k-1] <= a[k];
            }
            if (!ok) {
                SimpleOutput out = new SimpleOutput();
                out.println ("error:  insertion sort");
            }
        }
        
    } // quicksort

    private static void quicksortKernel (int [] a, int first, int last) {
        int left=first+1;
        int right=last;
        int temp;

        // move random element to first spot to handle ordered data
        int pivot = first + (int)Math.floor((last-first)*Math.random());
        temp = a[first];
        a[first] = a[pivot];
        a[pivot] = temp;

        while (right >= left) {
            // search left to find small array item
            while ((right >= left) && (a[first] < a[right]))
                right--;
            // search right to find large array item
            while ((right >= left) && (a[first] >= a[left]))
                left++;
            // swap large left item and small right item, if needed
            if (right > left) {
                temp = a[left];
                a[left] = a[right];
                a[right] = temp;
                left++;
                right--;
            }
        }
        // put a[first] in its place
        temp = a[first];
        a[first] = a[right];
        a[right] = temp;
        
        // recursively apply algorithm to a[first]..a[right-1] 
        // and a[right+1]..a[last], provided these segments contain >= 2 items
        if (first < right-1)
            quicksortKernel (a, first, right-1);
        if (right+1 < last)
            quicksortKernel (a, right+1, last);   
    } // quicksortKernel

    public static void main (String argv[]) {
        // declaration of variables
        SimpleInput in = new SimpleInput();
        SimpleOutput out = new SimpleOutput();

        int numReps = 500;       // number of times experiment completed
        int arraySize;           // size of current array
        int i, j, trial;         // index variables
        long startTime, endTime, elapsedTime; // var. to count milliseconds

        out.println ("Program to provide timing data for sort algorithms");
        out.print ("Enter size array to test: ");
        arraySize = in.readInt ();

        out.println ("Results are based on " + numReps 
                   + " repetitions of the experiment.");

        out.println ();
        out.println ("Results of experiments (all times in milliseconds)");
        out.println ("                      insertion");
        out.println ("data                    sort  quicksort");
        out.println (" set                    time    time");
        out.println();

        // setup array
        int[] a = new int [arraySize];
        int[] data = new int [arraySize];

        for (trial = 1; trial <= 3; trial++) {
            for (i = 0; i<arraySize; i++) {
                switch (trial) {
                case 1: data[i] = 2*i;
                        break;
                case 2: data[i] = (int)Math.floor(3*arraySize*Math.random());
                        break;
                case 3: data[i] = 2*arraySize - 2*i;
                        break;
                }
            }

            switch (trial) {
                case 1: out.print ("ascending data:  ");
                    break;
                case 2: out.print ("random data:     ");
                    break;
                case 3: out.print ("descending data: ");
                    break;
            }

            // process insertion sort and record time
            elapsedTime = 0;
            for (i = 0; i<numReps; i++) {
                for (j = 0; j < a.length; j++) 
                    a[j] = data[j];
                startTime = System.currentTimeMillis();
                insertionSort (a);
                endTime = System.currentTimeMillis();
                elapsedTime += endTime-startTime;
            }
            out.print ("\t" + elapsedTime);
                
            // process quicksort and record time
            elapsedTime = 0;
            for (i = 0; i<numReps; i++) {
                for (j = 0; j < a.length; j++) 
                    a[j] = data[j];
                startTime = System.currentTimeMillis();
                quicksort (a);
                endTime = System.currentTimeMillis();
                elapsedTime += endTime-startTime;
            }
            out.println ("\t" + elapsedTime);
        }
    } // main
} // sortTest