/** Array.java -- implementation of quicksort.
 */
import java.io.*;
import java.util.*;

public class Array
{
  private int [] a;

  // By default, prompt the user to enter integers on one line.
  // The array can be any size, so we'll use the StringTokenizer.
  public Array() throws IOException
  {
    System.out.print("Enter values for array:  ");
    BufferedReader kbd = new BufferedReader(new InputStreamReader(System.in));
    String line = kbd.readLine();

    // We have a choice.  Use an ArrayList, or tokenize the line twice.
    // To make the sorting algorithms simpler to read, and faster, I chose
    // the array implementation.  In realistic Java applications, we would
    // probably opt for the ArrayList or some more sophisticated data
    // structure.
    StringTokenizer tok = new StringTokenizer(line, " ");
    int numValues = 0;
    while (tok.hasMoreTokens())
    {
      tok.nextToken();
      ++numValues;
    }
    a = new int [numValues];
    tok = new StringTokenizer(line, " ");
    for (int i = 0; i < numValues; ++i)
      a[i] = Integer.parseInt(tok.nextToken());

    System.out.println("You entered:  " + this);
  }

  public Array(Array otherArray)
  {
    int length = otherArray.a.length;
    a = new int[length];
    for (int i = 0; i < length; ++i)
      a[i] = otherArray.a[i];
  }

  public void mergeSortStarter()
  {
    mergeSort(a, 0, a.length - 1);
  }

  // Merge sort and Quick sort are based on the idea of "divide, conquer
  // and combine"
  public void mergeSort(int [] a, int p, int r)
  {
    System.out.println("entering mergeSort with range " + p + ".." + r);
    if (p < r)
    {
      int q = (p + r) / 2;
      mergeSort(a, p, q);
      mergeSort(a, q + 1, r);
      merge(a, p, q, r);
    }
  }

  // For merging 2 sub-arrays, we assume that a[p..q] and a[p+1..r]
  // are sorted already themselves.  We need to merge these elements
  // to form a single larger sorted sub-array a[p..r].
  // Let's merge them temporarily into a new array b.
  // To make this merge work, we must keep track of where we are in the two
  // sub-arrays.  This is why we have variables leftHand and rightHand,
  // initialized to the starting points of the sub-arrays.
  public void merge(int [] a, int p, int q, int r)
  {
    System.out.println("Starting merge " + p + ".." + q + " and " + 
		       (q+1) + ".." + r);

    int [] b = new int[r-p+1];
    int leftHand = p;
    int rightHand = q + 1;
    for (int i = 0; i < b.length; ++i)
    {
      // We move an element from our left hand if it's smaller or if
      // our right hand is finished.  In our first "if" statement we test
      // for the condition that we should pick the number from the left
      // hand.  This will happen if there are no more numbers on the right,
      // or if we still have numbers on the left, and it's smaller than
      // the one on the right.
      if (rightHand > r ||
          leftHand <= q && a[leftHand] < a[rightHand])
      {
        b[i] = a[leftHand];
        ++leftHand;
	System.out.println("left hand case,  b[" + i + "] = " + b[i]);
      }
      else
      {
        b[i] = a[rightHand];
        ++rightHand;
	System.out.println("right hand case, b[" + i + "] = " + b[i]);
      }
    }
    // now copy the temporary b array into a sub-array within a.
    for (int i = 0; i < b.length; ++i)
      a[p+i] = b[i];

    System.out.println("At end of merge, array is " + this);
  }

  // The "real" quicksort function needs to know 3 things -- the array,
  // and the starting and ending points.  These the Driver doesn't know,
  // so we have this wrapping function here to formally invoke quicksort.
  public void quickSortStarter()
  {
    quickSort(a, 0, a.length - 1);
  }

  public void quickSort(int [] a, int p, int r)
  {
    System.out.println("Entering quick sort:  " + p + ".." + r);
    if (p < r)
    {
      int q = partition(a, p, r);
      quickSort(a, p, q);
      quickSort(a, q+1, r);
    }
  }

  /** We are given a sub-array a with a range of elements p..r, and we need
   *  to partition it in the spirit of "divide and conquer".  Let's call
   * the value of the first element "x".  We put all elements less than
   * x on the left side of the sub-array, and elements larger than x on
   * the right.  We return the location of the boundary between the low
   * and high regions.
   */
  public int partition(int [] a, int p, int r)
  {
    System.out.println("Starting partition " + p + ".." + r);
    int x = a[p];
    int i = p-1;
    int j = r+1;
    while(true)
    {
      do 
        --j;
      while(a[j] > x);
      do
	++i;
      while(a[i] < x);
        
      if (i < j)
      {
	System.out.println("swapping elements at " + i + " and " + j);
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
      else
      {
	System.out.println("partition " + p + ".." + r + " returns " + j +
			   "  array is " + this);
        return j;
      }
    }
  }

  public void stoogeSortStarter()
  {
    stoogeSort(a, 0, a.length - 1);
  }

  public void stoogeSort(int [] a, int left, int right)
  {
    System.out.println("entering stooge with " + left + ".." + right);
    if (a[left] > a[right])
    {
      System.out.println("swapping elements at " + left + " and " + right);
      int temp = a[left];
      a[left] = a[right];
      a[right] = temp;
    }
    if (left + 1 < right)
    {
      int oneThird = (right - left + 1) / 3;
      stoogeSort(a, left, right - oneThird);
      stoogeSort(a, left + oneThird, right);
      stoogeSort(a, left, right - oneThird);
    }
    System.out.println("end of stooge(" + left + ".." + right + "):  " + this);
  }

  public String toString()
  {
    String build = "";
    for (int i = 0; i < a.length; ++i)
	build += a[i] + " ";
    return build;
  }
}