CS 241 Lab #2: Timing Sorting Algorithms

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CS 241 Lab #2: Timing Sorting Algorithms

Lab #2: Timing Sort Algorithms

Assigned: Mon 2 Feb 04
Due: Wed 11 Feb 04

The assignment

This assignment will consist of three parts: in the first, you will write a simple "stopwatch" timer, based on an interface (which you should implement) and some supplied code. In the second, you will use your "stopwatch" to perform some basic timing tests of Java operations and loops. In the last part, you will combine the timing driver with code written by Prof. Weiss (at the Florida International University) to time some sorting algorithms. Note that it is not expected that you will understand the sorting algorithms themselves at this point: rather you need only be able to understand enough of the code to be able to insert the timers at the right points.

Part one: Timers and Stopwatches

We have been discussing interfaces and classes for some time in lecture: now is your opportunity to try them out in actual Java code!

Here is a Java interface description for a simple notion of a timer.

You should write a concrete class called StopWatch which implements this interface. You will need to know (of course) how to get the actual timings; you may find the code in this file (graciously supplied by Professor Orr) useful:

Timing.java

You should copy both of these files to your own directories, then create a project which has includes the Timer interface, your StopWatch class and some sort of main driving routine to test the StopWatch (see the next phase below for ideas).

Part two: some simple timings

For the next part of the lab, you should test out your StopWatch by using it to time some simple loops, keeping track of the results and presenting them in a table (rows might represent different loop limits, columns might represent different tasks). In particular, you should test all of the following tasks for loop limits of 100, 10,000 and 1,000,000 (but don't run any test that takes longer than a few minutes, i.e., don't waste time waiting too long):

a basic loop that does some printing;
a basic loop that does some simple arithmetic;
a basic outer loop that makes an assignment into an array of integers (make sure you create the array before you start timing).

When you are done gathering this information, write a short paragraph or two explaining what you found: were there any anomalies or unexplainable results?

Note: if you put all the blocks of code together for convenience, remember to "turn off" one block of code using comments before you "turn on" the next one.

Once you have run these basic tests, go back and try plotting out running times for the nested loop example for various numbers of iterations (you may use a drawing program, spreadsheet, statistical package or just graph paper). Try to determine what the shape of the curve is (linear, quadratic, cubic, etc.) and run further tests until you feel fairly confident about your answer.

Part three: timing sorting algorithms

For the second part of the lab, you should get Prof. Weiss' sorting package to run under NetBeans. This will require putting the various pieces together into a project and compiling all the parts. Once you have gotten this working, you should combine this with the Timer and StopWatch code from the first part of the lab. There are several ways you could make this combination, including just pasting the timing code in around the sort calls or making a more elaborate class structure so that you can call timer start and stop methods around any block of code you need to time (this would be preferable but may be a bit harder to design). Using a class structure and method calls will add a little bit of overhead to the timings, but presumably only a constant amount!

The sorting programs written by Prof. Weiss can be found at this link:

DataStructures directory

You will need all 4 of these Java files in order to compile the sorting code (i.e., MyInteger, Comparable, Sort and Random).

Once you are set to time some of Weiss' sort routines, run some tests sorting the same sizes of input using insertion sort, quicksort and one other sorting method of your choice. Use at least 4 sizes of input for each sorting algorithm (i.e., at least 12 runs all together). Record your timing data in a chart and write a short summary of what you found (which algorithm was best, which was worst, etc.). Try to characterize the behavior of the algorithms: are they linear, quadratic or something else?

A typical table of results might look something like this:

Algorithm	N = 100	N = 200	N = 500	N = 1,000
Insertion Sort	nnn	nnn	nnn	nnn
Quicksort	nnn	nnn	nnn	nnn
Heap Sort	nnn	nnn	nnn	nnn

Algorithm N = 100 N = 200 N = 500 N = 1,000

Insertion Sort nnn nnn nnn nnn

Quicksort nnn nnn nnn nnn

Heap Sort nnn nnn nnn nnn