import java.util.Date;
import java.util.Vector;

public class Sorter extends Vector<Number> {
  private void selectionsort () {selectionsort (0);}
  public void quicksort() {quicksort (0,size()-1,0);}
  public void mixedinsertionsort(int k) {
    // Sort using quicksort on list lengths > k
    // Sort using insertionsort on list lengths <= k
    quicksort (0,size()-1,k);
    insertionsort();
  }

  private void swap (int i, int j) {
    Number tmp = elementAt (i);
    setElementAt (elementAt (j), i);
    setElementAt (tmp, j);
  }
  private boolean less (int i, int j) {
    return ((elementAt(i)).doubleValue() < 
	    (elementAt(j)).doubleValue());
  }

  private void selectionsort (int low) {
    while (low < size()) {
      // Loop invariant:  The smallest elements are sorted to the left of 'low'.
      // Loop selects the next smallest, and shifts 'low' to the right.
      int min = low;
      for (int i = low+1; i < size(); i++)
	if (less (i, min)) min = i;
      swap (low, min);
      low++;
    }
  }

  private void insertionsort () {
  }

  private void quicksort (int i, int j, int k) {
    // Sort elements i through j, leaving lists of size <=k elements unsorted
  }

  public void print() {
    for (int i = 0; i < size(); i++)
      System.out.print (elementAt (i) + " ");
    System.out.println();
  }

  public static boolean equals(Sorter s, Sorter t) {
    if (s.size() != t.size()) return false;
    for (int i = 0; i < s.size(); i++) {
      if (!((Integer) s.elementAt(i)).equals((Integer) t.elementAt(i))) {
      //      if (s.elementAt(i) != t.elementAt(i)) {
	System.out.println ("Position " + i + " s:" + s.elementAt(i) + " t:" + t.elementAt(i));
	return false;
      }
    }
    return true;
  }

  public static void testEquals(Sorter s, Sorter t) {
    if (!equals (s,t)) {
      System.out.println ("Vectors aren't equal: ");
      s.print();
      t.print();
    }
  }

  public static void test() {
    Sorter original = new Sorter();
    for (int i = 0; i < 20; i++)
      original.addElement(new Integer((int) (Math.random() * 100)));
    Sorter quick = (Sorter) original.clone();
    quick.quicksort();
    Sorter test;

    test = (Sorter) original.clone();
    test.insertionsort();
    testEquals (quick, test);

    test = (Sorter) original.clone();
    test.selectionsort();
    testEquals (quick, test);

    test = (Sorter) original.clone();
    test.mixedinsertionsort(5);
    testEquals (quick, test);
    System.out.println ("Test complete");
  }
  
  public static void time(Sorter s, int k) {
    // Just a wrapper around findRandomPrime to output timing information
    Sorter t = (Sorter) s.clone();
    int count;

    long before = new Date().getTime();
    for (count = 0; count <= 50; count++) {
      for (int i = 0; i<s.size(); i++)
	t.setElementAt(s.elementAt(i), i);
      t.mixedinsertionsort(k);
    }
    long after = new Date().getTime();
    System.out.println (k + "\t" + (after - before) / (double) count);
  }

  public static void main (String argv[]) {
    test();
    Sorter s = new Sorter();
    for (int i = 0; i < 100; i++)
      s.addElement(new Double(Math.random()));
    System.out.println ("Mixed insertion sort:");
    System.out.println ("k" + "\t" + "time");
    for (int k = 1; k < 20; k++)
      time(s, k);
  }
}