/** 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 long 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;
    }


  // 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 String toString()
  {
    String build = "";
    for (int i = 0; i < a.length; ++i)
	build += a[i] + " ";
    build += "(" + ops + " operations)";
    return build;
  }

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

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

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

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