/** Array.java -- This is the place where we get to play with arrays --
 *  create them and sort them in various ways.  (changed to make ascending)
 */
import java.io.*;
import java.util.*;

public class Array
{
  private int [] a;
  private int ops;

  // 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());
    ops = 0;
  }

  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];
    ops = 0;
  }

  // Constructor that the tester class can use on "true" arrays
  public Array(int [] otherArray)
  {
    int length = otherArray.length;
    a = new int[length];
    for (int i = 0; i < length; ++i)
      a[i] = otherArray[i];
    ops = 0;
  }

  // This constructor takes an integer (how many) and a String (values)
  public Array(int n, String s)
  {
    a = new int[n];
    StringTokenizer tok = new StringTokenizer(s, " ");
    for (int i = 0; i < n; ++i)
      a[i] = Integer.parseInt(tok.nextToken());
    ops = 0;
  }


  // Swap sort -- this one says to look at each distinct pair of elements,
  // and swap any that are out of order.
  public void swapSort()
  {
    int i, j;
    for (++ops, i = 0; ++ops>0 && i < a.length; ++ops, ++i)
      for (++ops, j = i+1; ++ops>0 && j < a.length; ++ops, ++j)
      {
	++ops;
        if (a[i] > a[j])
        {
	  ops += 3;
          int temp = a[i];
          a[i] = a[j];
          a[j] = temp;
	}
      }
  }

  // Selection sort:
  // For each position i in the array except the last 0..n-2,
  // find the *smallest* element from i..n-1 and swap it into position i.
  public void selectionSort()
  {
    int i, j;
    for (++ops, i = 0; ++ops>0 && i < a.length - 1; ++ops, ++i)
    {
      // find the location of the largest element from i to the end
      ++ops;
      int smallestElement = i;
      for (++ops, j = i+1; ++ops>0 && j < a.length; ++ops, ++j)
      {
        ++ops;
        if (a[j] < a[smallestElement])
        {
	  ++ops;
	  smallestElement = j;
	}
      }

      // I think most of the time the largest element will not already
      // be in position, so let's just go ahead and swap them without
      // asking if it's necessary.
      ops += 3;
      int temp = a[i];
      a[i] = a[smallestElement];
      a[smallestElement] = temp;
    }
  }

  // Insertion sort:  Initially assume position 0 is sorted.
  // For each position i from 1..n-1, see how far left i can be inserted.
  // We'll need an inner loop to move elements right to make room for i.
  public void insertionSort()
  {
    int i, j;
    for (++ops, i = 1; ++ops>0 && i < a.length; ++ops, ++i)
    {
      // put a[i] in a temporary place until we find its resting place
      ++ops;
      int temp = a[i];
      for (++ops, j = i-1; 
           ++ops>0 && j >= 0 && ++ops>0 && a[j] > temp; 
           ++ops,--j)
      {
        ++ops;
        a[j+1] = a[j];
      }

      // By the time we are done with the loop, j is pointing to a number
      // that didn't need to move, so j+1 is where we need to insert.
      ++ops;
      a[j+1] = temp;
    }
  }

  // In Bubble Sort, we do the following n-1 times:
  // For each element i from 0..n-2, compare it to its neighbor i+1, and
  // swap if necessary.
  public void bubbleSort()
  {
    int pass, i;
    for (++ops, pass = 0; ++ops>0 && pass < a.length - 1; ++ops, ++pass)
    {
      for (++ops, i = 0; ++ops>0 && i < a.length - 1; ++ops, ++i)
      {
	++ops;
        if (a[i] > a[i+1])
  	{
	  ops += 3;
          int temp = a[i];
	  a[i] = a[i+1];
	  a[i+1] = temp;
	}
      }
    }
  }

  public void mergeSortStarter()
  {
    ops = 0;
    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);
    ++ops;
    if (p < r)
    {
      ops += 6;
      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)
  {
    int i;
    //System.out.println("Starting merge " + p + ".." + q + " and " +
    //         (q+1) + ".." + r);

    int [] b = new int[r-p+1];
    ops += 2;
    int leftHand = p;
    int rightHand = q + 1;
    for (++ops, i = 0; ++ops>0 && i < b.length; ++ops, ++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 ((++ops>0 && rightHand > r) ||
	  ++ops>0 && leftHand <= q && ++ops>0 && a[leftHand] < a[rightHand])
      {
	ops += 2;
	b[i] = a[leftHand];
	++leftHand;
	//System.out.println("left hand case,  b[" + i + "] = " + b[i]);
      }
      else
      {
	ops += 2;
	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 (++ops, i = 0; ++ops>0 && i < b.length; ++ops, ++i)
    {
      ++ops;
      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()
  {
    ops = 0;
    quickSort(a, 0, a.length - 1);
  }

  public void quickSort(int [] a, int p, int r)
  {
    //System.out.println("Entering quick sort:  " + p + ".." + r);
    ++ops;
    if (p < r)
    {
      ops += 4;
      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);
    ops += 3;
    int x = a[p];
    int i = p-1;
    int j = r+1;
    while(true)
    {
      do
      {
	ops += 2;
        --j;
      } while(a[j] > x);
      do
      {
        ops += 2;
        ++i;
      } while(a[i] < x);
      ++ops;
      if (i < j)
      {
	ops += 3;
        //System.out.println("swapping elements at " + i + " and " + j);
        int temp = a[i];
	a[i] = a[j];
        a[j] = temp;
      }
      else
      {
        ++ops;
        //System.out.println("partition " + p + ".." + r + " returns " + j +
        //                 "  array is " + this);
        return j;
      }
    }
  }

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

  public int getSwapOps()
  {
    ops = 0;
    swapSort();
    return ops;
  }

  public int getSelectionOps()
  {
    ops = 0;
    selectionSort();
    return ops;
  }

  public int getInsertionOps()
  {
    ops = 0;
    insertionSort();
    return ops;
  }

  public int getBubbleOps()
  {  
    ops = 0;
    bubbleSort();
    return ops;
  }

  public int getMergeOps()
  {
    ops = 0;
    mergeSortStarter();
    return ops;
  }

  public int getQuickOps()
  {
    ops = 0;
    quickSortStarter();
    return ops;
  }

}