This lab explores various sorting algorithms and uses the Plotter java
applet to graph their running times.

As usual, mail me your lab work as a text file when you're done.
Also, make a directory for this lab.

1) In ~lorenz/cs35-2/lab5/ you'll find java code for four sorting algorithms:

	bubble.java     insertion.java  merge.java      selection.java  

   Copy these files into your directory and inspect the algorithms.  The 
   merge sort (merge.java) is essentially the one presented in lecture.

   For each sort, compile the java file and test the sort by running "main"
   in each class.  (Testing has been built into the classes for you.)
   Examine the sort input (String arrays) and make sure the output is 
   correctly sorted for the four algorithms.

2) Copy the files names.java, Main.java, Plotter.java and applet.html to
   your directory.  Compile the .java files in the above order.  Inspect
   Main.java -- it should look very familiar.

   names.java provides a random array of strings (login names) via the 
   .shuffle(int n) method; the parameter "n" is the size of the array to 
   return (must be less than 350 or so).

   Plotter.java draws the graphs of functions and applet.html is the file
   you load into "hotjava" to run Main.main and to call the plotter.

3) After everything is compiled, load applet.html into "hotjava".
   You should see a cyan line representing the n(log n) function.

4) Each sorting algorithm has a static integer variable n_comparisons
   that we'll use to count the number of comparisons a sort executes
   on sample name data.  For the merge sort, identify where comparisons
   occur and, for each, increment n_comparisons by one.

   Recompile and reload the applet.  You should now see a blue curve for
   the merge-sort running time (as # of comparisons).

5) For the remaining three sorts, add "Measure<sortname>" classes (copy
   MeasureMerge to get started) and identify where comparisons happen
   in the sort's code and increment the n_comparisons variable there.

   As you add a sort, extend the_functions in Main.main, recompile, and
   test the applet.  You may want to use separate colors for the new
   curves (see on-line docs for java.awt.Color for choices).

   Based on n_comparisons, which sort is the fastest? Slowest?

6) For each of the four sorts, consult your lecture notes and add to the
   plot the corresponding worst-case runtime curve.  Note: since big-O
   abstracts constants and counting n_comparisons doesn't, it could 
   happen that the mathematical function lies below the actual counts;
   their shape, however, should be very similar.

7) Now, we'll explore linear and binary search.  First, copy the file 
   search.java to your directory, compile it, and study it.  It contains
   a linear search (for unsorted arrays) and a binary search (for sorted
   arrays).  You may need to sit down with the binary search outside of
   lab to fully understand it.

8) The Search class contains the static variable "n_probes"; as with
   "n_comparisons" in the sorting algorithms above, instrument "linear"
   and "binary" to tally the number of .compareTo method invocations.

9) Next, create classes in Main.java to measure the running time (as number
   of probes) of the linear and binary searches; make the appropriate
   modification of "myname" as indicated:

	class MeasureLinear extends MeasureSort {
	  MeasureLinear() {
	    Names n = new Names();
	    pts = new int[nPts];
	    String myname = "<your login name goes here>"; //CHANGE THIS

	    for (int i = 1; i < nPts; i++) {
	      String some_names[] = n.shuffle(i,myname);  
	 
	      Search.n_probes = 0;
              /* note: no sort; search unordered array */
	      Search.linear(myname,some_names);
	      pts[i] = Search.n_probes;
            }
          }
        }


	class MeasureBinary extends MeasureSort {
	  MeasureBinary() {
	    Names n = new Names();
	    pts = new int[nPts];
	    String myname = "<your login name goes here>"; //CHANGE THIS

	    for (int i = 1; i < nPts; i++) {
	      String some_names[] = n.shuffle(i,myname);  

	      Search.n_probes = 0;	
              MergeSort.sort(some_names);  //any sort will do here

	      Search.binary(myname,some_names);
	      pts[i] = Search.n_probes;
            }
          }
        }

10) Hook the new classes into the_functions and plot them.

11) Add functions for the average-case and worst-case running times
    of the two searches.

12) Go back to 4) and 5) and in addition to counting comparisons, also
    count assignment statements (e.g. "a[i] = tmp" should increment some
    new variable declared similarly to "n_comparisons").  Plot these 
    curves as well.