import cs101.terminal.*;

public class Quicksort {
  public static void main(String args[]) {
    Terminal.startTranscript("transcript.txt");
    int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};   // test input in reverse order
    sort(a);
    int[] b = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};   // test input already sorted
    sort(b);
    int[] c = {8, 5, 3, 2, 9, 6, 4, 1, 0, 7};   // test input scrambled
    sort(c);
    int[] d = {8, 5, 3, 2, 9, 3, 4, 1, 3, 7};   // test input with duplicate elements
    sort(d);
    Terminal.stopTranscript();
  }

  public static void sort(int[] a) {
    Terminal.println("\n\nSorting... ");
    quicksort(a, 0, a.length-1);
    Terminal.println(showArray(a));
  }

  static void quicksort(int[] a, int low, int high) {
    if (low < high) {                         // if there are at least two elements to sort
       int middle = partition(a, low, high);  //   partition into smaller and larger elements
       quicksort(a, low, middle-1);           //   sort the smaller elements
       quicksort(a, middle+1, high);          //   sort the larger elements
    }
  }

  static int partition(int[] a, int low, int high) {
    Terminal.println(showArray(a));
    Terminal.println("partition from " + low + " to " + high);
    int pivot = a[high];               // use the rightmost element as the pivot
    int smallSide = low;               // keep track of the small side (grow from the left)
    int largeSide = high-1;            // keep track of the large side (grow from the right)

    while (smallSide < largeSide) {    // as long as the two sides don't meet
        while (a[smallSide] < pivot)   //   grow the small side as much as possible
           smallSide++;
        while (largeSide >= 0 &&       //   grow the large side as much as possible
               pivot <= a[largeSide])
           largeSide--;
        if (smallSide < largeSide)     //   if the sides didn't meet
           swap(a,smallSide,largeSide);  //      swap their boundary elements
    }

    int pivotLocation;
    if (pivot < a[smallSide]) {        // finally, put the pivot into position
       swap(a,smallSide,high);
       pivotLocation = smallSide;
    } else {
       pivotLocation = high;
    }

    Terminal.println("pivot is at " + pivotLocation);
    return pivotLocation;
  }

  static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  static String showArray(int[] a) {
    String result = "";
    for (int i = 0; i < a.length; i++) {
        result = result + a[i] + " ";
    }
    return result;
  }
}