Albany Programming Course Supplement

Timing

Here is a handy Java class for objects that function as stopwatches. I found out about the java.util.Date class from the Java API reference.

import java.util.Date;
class Stopwatch
{
  private long timeStarted; //Units are milliseconds.
  public void reset()
  {
    timeStarted = new Date().getTime();
  }
  public Stopwatch()
  {
    reset();
  }
  public long elapsed()
  {
    return new Date().getTime() - timeStarted;
  }
  public void print()
  {
    System.out.println("Elapsed Time: " + elapsed()/1000.0
                        + " seconds.");
  }
}

The following Java application uses the Stopwatch class to help observe how fast are two alternative algorithms for sorting.

import java.util.Scanner;
public class SortableArray
{
  private int[] theArray;

  private int[] scratch;

  SortableArray(int[] x)
  {
    theArray = x;
  }

  public void sortMerge()
  {
    scratch = new int[theArray.length];
    sortMerge(0, theArray.length-1);
  }

  private void sortMerge(int from, int to)
  {
    if(from < to)
    {
      int mid = (from + to)/2;
      sortMerge(from, mid);
      sortMerge(mid+1, to);
      Merge(from,mid,mid+1,to);
    }
  }

  private void Merge(int from1, int to1, int from2, int to2)
  {
    int src1 = from1;
    int src2 = from2;
    for(int dest = from1; dest <= to2; dest++)
    {
      if(src1 <= to1 && src2 <= to2)
      {
         if(theArray[src1] < theArray[src2])
         {
            scratch[dest] = theArray[src1++];
         }
         else
         {
            scratch[dest] = theArray[src2++];
         }
      }
      else
      {
        if(src1 <= to1)
          scratch[dest] = theArray[src1++];
        if(src2 <= to2)
          scratch[dest] = theArray[src2++];
      }
    }
    for(int dest = from1; dest <= to2; dest++)
    {
      theArray[dest] = scratch[dest];
    }
  }


  public void sortSelection()
  {
    System.out.println("sortSelection called.");
    for(int out = 0; out != theArray.length-1; out++)
    {
      for(int scanpos = out+1; scanpos < theArray.length; scanpos++)
      {
        if(theArray[out] > theArray[scanpos])
        {
           int temp;
           temp = theArray[out];
           theArray[out] = theArray[scanpos];
           theArray[scanpos] = temp;
        }
      }
    }
        System.out.println("sortSelection returns.");
  }

  private static void printArray(int[] x)
  {
    for(int i = 0; i < x.length; i++)
      System.out.println(x[i]);
  }

  public static void main(String[] arg)
  {
    Scanner sc = new Scanner(System.in);
    System.out.print("How many ints to sort?");
    int nToSort = sc.nextInt();
    int[] myArray = new int[nToSort];
    for(int i=0; i< 10) printArray(myArray);

    SortableArray mySorter = new SortableArray(myArray);
    System.out.print("Which algorithm? selection or mergesort:");
    sc.nextLine(); //Gobble the empty line after the number previously read.
    String response = sc.nextLine();
    Stopwatch sw = new Stopwatch();
    if(response.equals("selection"))
      mySorter.sortSelection();
    else if(response.equals("mergesort"))
      mySorter.sortMerge();
    else
    {
      System.out.println("Unrecognized algorithm name.");
      return ;
    }
    sw.print();
    System.out.println("After " + response + ":\n");
    if(nToSort < 10) printArray(myArray);
  }
}

Exercise: Modify the SortableArray class so that, after you select the algorithm, you specify a maximum length of an array to sort. Then, it does the timing on arrays of size 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, etc. up to the maximum length you specify. Use your program to generate the timings for both algorithms for larger and larger arrays up to sizes for which it is reasonable for you to wait for the results. Plot the results on a log-log graph. (Explanation and grid for printing to be supplied).