import edu.princeton.cs.algs4.*;

public class PlotRunningTimes {

    public static double timeInsertionSort(int arraySize, int numTrials, long seed) {
        // Hér er ráðlagt (en ekki nauðsynlegt) að skrifa aðferð skv. lýsingu:
        /*
        Skilar meðalkeyrslutíma innsetningarröðunar á slembifylki af stærð <arraySize>
        eftir <numTrials> keyrslur, með slembitölugjafann stilltan á <seed>.
         */
    	double y = 0;
    	StopwatchCPU timi;
    	Double[] x;

        for(int i=0; i<numTrials; i++) {

        	timi = new StopwatchCPU(); // búum til skeiðklukku

	    	x = new Double[arraySize];
	    	StdRandom.setSeed(seed);
	    	for (int j=0; j<x.length; j++) {
	    		x[j] = StdRandom.uniform();
	    	}

	    	Insertion.sort(x);

	    	y += timi.elapsedTime(); // tíminn frá því að skeiðklukkan varð til
        }

        y /= numTrials; //meðaltal
        System.out.println(y);
    	return y;
    }

    public static void main(String[] args) {
        /* Skilgreining gagna */

        int maxArraySize = 5000; // Mesta stærð á fylki sem við ætlum að tímamæla
        int stride = 10; // Bil á milli stærða
        int numTrials = 20; // Fjöldi mælinga fyrir hverja stærð fylkis
        long seed = 203; // Fastur grunnur fyrir slembitölugjafann


        for (int i=maxArraySize; i>0; i-=stride) {

            double a = timeInsertionSort(i, numTrials, seed); // mælingar
            System.out.println(i);

            if (i == maxArraySize) { // skilgreinum x og y-ás
            	StdDraw.setXscale(0, maxArraySize);
            	StdDraw.setYscale(0, a);
            	StdDraw.setPenRadius(0.005);
            }

            StdDraw.point(i, a); // teiknum punkt
        }

    }

}