import edu.princeton.cs.algs4.*;
import java.util.*;
import java.lang.*;
/**
 *
 * @author Gustaf Bjering
 *
 * Following program tests and measures the execution times for sorting algorithms
 * insertionsort, mergesort and quicksort for different input sizes N and computes an
 * average for these. Arrays are generated by different seeds which is used for filling
 * the arrays to be sorted with random integers.
 */
public class LEAssignment2Ver2 {
    static int N;
    static int K;
    static double[] execTimes = new double[3];


    public static void main(String[] args) {

      System.out.println("Enter a the number of integers to generate for the array: \n");
      N = StdIn.readInt();
      int arg = Integer.parseInt(args[0]);
      K = arg;

      System.out.println("Results for test with Insertion, Merge " +
        "and Quick sort with length " + N +  ":");


      runAlgorithms();


      printResults();

  }

  // method takes an argument long as seed for Random function which generates different
  // values of ints and puts them to array and returns that array
  public static int[] generateArray(long seed) {
      int val;
      int[] arr = new int[N];
      for(int i = 0; i < N; i++) {
        Random generator = new Random(seed);
        val = Math.abs(generator.nextInt(K) + 1);

        arr[i] = val;
        seed--;
      }
      return arr;
  }



  public static void printResults() {
      System.out.println("Sorting " + N + " elements for mergeSort average time " + execTimes[0]);
      System.out.println("Sorting " + N + " elements for quickSort average time "  + execTimes[1]);
      System.out.println("Sorting " + N + " elements for insertionSort average time "  + execTimes[2] + "\n");

  }


  // method that runs and measures execution times for sorting merge, quick and insertion sort
  // for 14 different sizes of arrays generated by different seeds
  public static void runAlgorithms() {
      int[] arr;
      // seed generated by function currentTimeMillis
      long seed = System.currentTimeMillis();

      //test for mergesort
      arr = generateArray(seed);
      long start1 = System.nanoTime();
      mergeSort(arr);
      long end1 = System.nanoTime();
      double time1 = (((double) (end1 - start1)) * (Math.pow(10, -9)));
      execTimes[0] += time1;

      //test for quicksort
      arr = generateArray(seed);
      long start2 = System.nanoTime();
      quickSort(arr, 0, arr.length - 1);
      long end2 = System.nanoTime();
      double time2 = (((double) (end2 - start2)) * (Math.pow(10, -9)));
      execTimes[1] += time2;


      //test for insertionsort
      arr = generateArray(seed);
      long start3 = System.nanoTime();
      insertionSort(arr);
      long end3 = System.nanoTime();
      double time3 = (((double) (end3 - start3)) * (Math.pow(10, -9)));
      execTimes[2] += time3;


  }


  public static void insertionSort(int[] arr) {
      int var;
      // iterates array through from second element of the array
      for (int i = 1; i < arr.length; i++) {

          // swap adjacent elements at position j and j-1 until element at position
          // j is smaller than element at position j-1
          for (int j = i; j > 0 && (arr[j-1] > arr[j]); j--) {
              // swap adjacent elements
              var = arr[j-1];
              arr[j-1] = arr[j];
              arr[j] = var;

          }
      }
  }


  private static int[] mergeSort(int[] arr) {
    // return if array only has one element
    if(arr.length <= 1) {
          return arr;
    }

    int mid = arr.length / 2;


    int[] left = new int[mid];
    // if input array has un-even length assert the un-even part to second sub array
    int[] right = arr.length % 2 == 0 ? new int[mid] : new int[mid + 1];

    // copy elements from input array to left and right sub array
    for(int i = 0; i < arr.length ; i++) {
        if(i <= mid-1) {
            left[i] = arr[i];
        } else {
            right[i - mid] = arr[i];
        }
    }

    // continue to divide left and right sub array until all sub arrays has one element
    left = mergeSort(left);
    right = mergeSort(right);

    // merge arrays
    return merge(left, right);

  }

  private static int[] merge(int[] left, int[] right) {
    int leftPoint, rightPoint, resPoint;
    leftPoint = rightPoint = resPoint = 0;
    int[] res = new int[left.length + right.length];

    //if there is elements in either the left, or the right array
    while(leftPoint < left.length || rightPoint < right.length){

          //if there exists elements in both arrays
          if(leftPoint < left.length && rightPoint < right.length) {


              //depending on which element that is greater, assert
              //the minor one to the resulting array and increment by 1
              if(left[leftPoint] < right[rightPoint]) {
                  res[resPoint++] = left[leftPoint++];
              } else {
                  res[resPoint++] = right[rightPoint++];
              }
          }
          else if(leftPoint < left.length) {
              res[resPoint++] = left[leftPoint++];
          }
          else if(rightPoint < right.length) {
              res[resPoint++] = right[rightPoint++];
          }

    }
    return res;
  }


  private static void quickSort(int[] a, int lo, int hi) {
    if((a.length > 1) && (lo < hi)) {

        int position = partition(a, lo, hi);

        quickSort(a, lo, position - 1);
        quickSort(a, position + 1, hi);
      }

  }

  // partitions sub array left <----> right so that element the last element in
  // the array is at a position where elements right of it is greater and elements at left
  private static int partition(int[] a, int lo, int hi) {

        int pivotVal = a[hi];
        int i = lo - 1;

        for(int j = lo; j <= hi - 1; j++) {
            if(a[j] <= pivotVal) {
                i++;

                int val = a[i];
                a[i] = a[j];
                a[j] = val;
            }
        }

        int p = a[i + 1];
        a[i + 1] = a[hi];
        a[hi] = p;

        return i + 1;
    }


  }