// Dynamic Array for sort routines

import java.lang.reflect.Array;

class DynamicArray {
  private Comparable[] arr; //array for comparable objects
  private int elems; //number of elements in array
  private static final int CAPACITY = 10;

  //default constructor
  DynamicArray() {
     arr = new Comparable[CAPACITY]; //allocate space
     elems = 0; //set number of elements to 0
  }

  //return the size of working array
  public int size() {
      return elems;
  }

  //return memory
  public void destroy() {
      arr = null; //de-referencing arr
      System.gc(); //force garbage collector
  }

  //insert item into arr - expand arr's size if necessary
  public void insert(Comparable value) {
      if(elems > arr.length-1) {
          Comparable[] list = (Comparable[])increaseSpace(arr);
          arr = list;
      }
      arr[elems] = value;
      elems++;
  }
 
  //double the size of array
  private Object increaseSpace(Object source) {
      int length = Array.getLength(source);
      Class arrayClass = source.getClass();
      Class componentClass = arrayClass.getComponentType();
      Object result = Array.newInstance(componentClass,
                                        length * 2);
      System.arraycopy(source, 0, result, 0, length);
      return result;
  }

  //printing objects in working array to standard output
  //in format: (x, x, x, x, ...)
  public void display() {
      System.out.print("(" + arr[0]);
      for(int i = 1; i < elems; i++)
          System.out.print(", " + arr[i]);
      System.out.println(")");
  }

  //printing via System.out.println() with
  //10 items per line
  public String toString() {
      StringBuffer buf = new StringBuffer();
      for(int i = 0; i < size(); i++) {
          if(i % 10 == 0)
             buf.append("\n");
          buf.append("\t" + arr[i]);
      }
      return new String(buf);
  }

  //exchange object at m and n
  private void swap(int m, int n) {
      Comparable temp = arr[m];
      arr[m] = arr[n];
      arr[n] = temp;
  }


  //bubble sort
  public void bubbleSort() {
      int current = 0, last = elems-1, walker;
      boolean sorted = false;

  //going forward
  while(current <= last && sorted == false) {
      walker = last;
      sorted = true;
      //going backward
      while(walker > current) {
          //comparing two adjacent elements
          //exchange positions if element at higher index
          //greater than the one at lower index
          if(arr[walker].compareTo(arr[walker-1]) < 0) {
              sorted = false;
              swap(walker, walker-1);
           }
           walker--; //move down one position
       }
       //display(); //show content after one pass
       current++; //move up one position
    }
  }

  //insertion sort
  public void insertionSort() {
      int current, walker;
      Comparable hold;

      for(current = 1; current < elems; current++) {
          //hold stores data at current position
          //walker starts at current position
          //compare data at walker-1 with hold
          //exchange positions of data if necessary
          hold = arr[current];
          walker = current;
          while(walker > 0 &&
                arr[walker-1].compareTo(hold) >= 0) {
              arr[walker] = arr[walker-1];
              walker--;
          }
          arr[walker] = hold;
          //display();
      }
  }

  //selection sort
  public void selectionSort() {
      //current starts at 0, last = last index of array
     int current = 0, last = elems-1;
     int walker, smallest;

     //loop until all data is in place
     while(current < last) {
         //assume smallest is at current
         //and set walker to the one next to it
         smallest = current;
         walker = current + 1;
         //compare all elements to the right with smallest
         //until one smaller than smallest is found
         while(walker <= last) {
             if(arr[walker].compareTo(arr[smallest]) < 0)
                 smallest = walker;
             walker++;
         }
         //exchange data at current and smallest since
         //the one at current is the smallest one
         swap(current, smallest);
         //display();
         current++;
      }
   }
 }