import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * Quicksort solution by Arne Maus
 */
public class Uke8_oppg2 {
    public static final int LIMIT = 32;          // Limit in quicksort
    public static final int BIG_LIMIT = 100000;  // Limit in quicksort
    public static final int MIN_NUM = 100;       // Miminum number of elements to sort
    public static final int MAX_NUM = 10000000;  // Maximum numbers of elements to sort
    public static final int NUM_TESTS = 3;       // Number of tests for each N (median times)

    public static void main(String[] args) {
        Uke8_oppg2 u = new Uke8_oppg2();
        u.runTests();
    }

    public void runTests() {
        int[] randomArr = null;
        long start;

	// Used to store final times for each N
        ArrayList<Double> seqTimes = new ArrayList<>();
        ArrayList<Double> parTimes = new ArrayList<>();

	// Used to store temporary times for the inner loop
	double[] seqTestTimes = new double[NUM_TESTS];
	double[] parTestTimes = new double[NUM_TESTS];

        for (int n = MAX_NUM; n >= MIN_NUM; n /= 10) {
            for (int i = 0; i < NUM_TESTS; i++) {
                /********  PARALLEL ************/
                randomArr = createAndfillWithRandomNumbers(n);
                start = System.nanoTime();
                quicksortPar(randomArr, 0, randomArr.length-1); // inclusive right, so we have to subtract one
                parTestTimes[i] = (System.nanoTime() - start)/1000000.0;

                /******** SEQUENTIAL ***********/
                randomArr = createAndfillWithRandomNumbers(n);
                start = System.nanoTime();
                quicksortSeq(randomArr, 0, randomArr.length-1); // inclusive right, so we have to subtract one
                seqTestTimes[i] = (System.nanoTime() - start)/1000000.0;
            }

	    Arrays.sort(seqTestTimes);
	    Arrays.sort(parTestTimes);

	    // Add median time for this N
	    seqTimes.add(seqTestTimes[seqTestTimes.length/2]);
	    parTimes.add(parTestTimes[parTestTimes.length/2]);
        }

        printTimes(seqTimes, parTimes);
    }

    public void printTimes(ArrayList<Double> seqTimes, ArrayList<Double> parTimes) {
        System.out.println("     n    sekv.tid(ms)  para.tid(ms)  Speedup");
        int i = 0;
        for (int n = MAX_NUM; n >= MIN_NUM; n /= 10, i++) {
            System.out.printf("%9d %12.2f %12.2f %7.2f\n", n, seqTimes.get(i), parTimes.get(i), seqTimes.get(i)/parTimes.get(i));
        }
    }

    public int[] createAndfillWithRandomNumbers(int size) {
        Random rand = new Random(5233);
        int[] a = new int[size];

        for (int i = 0; i < a.length; i++) {
            a[i] = rand.nextInt(a.length);
            //    System.out.println("a[" + i + "] = " + a[i]);
        }

        return a;
    }

    void quicksortSeq(int[] a, int left, int right) {
        if (left < right) {
            if (right - left < LIMIT) {
                insertSort(a,left,right);
            } else {
                int pivotIndex = partition(a, left, right);
                int pivotIndex2 = pivotIndex - 1, pivotVal = a[pivotIndex];

                while (pivotIndex2 > left && a[pivotIndex2] == pivotVal){
                    pivotIndex2--;
                }

                quicksortSeq(a, left, pivotIndex2);
                quicksortSeq(a, pivotIndex + 1, right);
            } // end else
        } // end if
    } // end quicksort

    void quicksortPar(int[] a, int left, int right) {
        if (left < right) {
            if (right - left < LIMIT) {
                insertSort(a,left,right);
            } else {
                int pivotIndex = partition(a, left, right);
                int pivotIndex2 = pivotIndex - 1, pivotVal = a[pivotIndex];

                while (pivotIndex2 > left && a[pivotIndex2] == pivotVal){
                    pivotIndex2--;
                }

                Thread t1 = null;
                if (right - left <= BIG_LIMIT) {
                    quicksortPar(a, left, pivotIndex2);
                } else {
                    t1 = new Thread(new QuickPara(a, left, pivotIndex2));
                    t1.start();
                }

                // use same thread on right branch
                quicksortPar(a, pivotIndex + 1, right);

                if (t1 != null) {
                    try {
                        t1.join ();
                    } catch (InterruptedException e ) {
                        return;
                    }
                }
            } // end else
        } // end if
    } // end quicksort


    int partition (int[] a, int left, int right) {
        int pivotValue = a[(left+ right) / 2];

        swap(a,(left+ right) / 2, right);
        int index = left;

        for (int i = left; i < right; i++) {
            if (a[i] <= pivotValue) {
                swap(a, i, index);
                index++;
            }
        }
        swap(a, index, right);
        return index;
    } // end partition

    void swap (int[] a, int left, int right) {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    } // end swap

    void insertSort(int a[],int l, int r) {
        int i, t;
        for (int k = l ; k < r; k++)
            if (a[k] > a[k+1]) {
                t = a[k+1];
                i = k;
                while (i >= 0 && a[i] > t) {
                    a[i+1] = a[i]; i--;
                }
                a[i+1] = t;
            }
    }


    class QuickPara implements Runnable {
        final int left, right;
        final int[] a;

        QuickPara(int[] a, int left, int right) {
            this.a = a;
            this.left = left;
            this.right = right;
        }

        public void run() {
            quicksortPar(a, left, right);
        }
    }
}