/** Array.java -- This is the place where we get to play with arrays --
 *  create them and sort them in various ways.
 */
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());
  }

  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];
  }

  // Swap sort -- this one says to look at each distinct pair of elements,
  // and swap any that are out of order.
  public void swapSort()
  {
    for (int i = 0; i < a.length; ++i)
      for (int j = i+1; j < a.length; ++j)
      {
        if (a[i] < a[j])
        {
          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 largest element from i..n-1 and swap it into position i.
  public void selectionSort()
  {
    for (int i = 0; i < a.length - 1; ++i)
    {
      // find the location of the largest element from i to the end
      int largestElement = i;
      for (int j = i+1; j < a.length; ++j)
        if (a[j] > a[largestElement])
	  largestElement = 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.
      int temp = a[i];
      a[i] = a[largestElement];
      a[largestElement] = 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()
  {
    for (int i = 1; i < a.length; ++i)
    {
      // put a[i] in a temporary place until we find its resting place
      int temp = a[i];
      int j;
      for (j = i - 1; j >= 0 && a[j] < temp; --j)
        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.
      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()
  {
    for (int pass = 0; pass < a.length - 1; ++pass)
    {
      for (int i = 0; i < a.length - 1; ++i)
        if (a[i] < a[i+1])
  	{
          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] + " ";
    return build;
  }
}