Computer Science 410: Homework 3
Versions of Quicksort: A Computer Exercise

Homework 3: Handed out: 2/11/99; Due: 2/25/99

Note: This assignment involves programming, which will have to be done using J++ in the CSUGLab. If you haven't set up an account there yet, check the course web page for info. There will also be two short Java tutorials on Friday (Feb. 12), from 12-1 and from 4:30-5:30. The tutorials will be held in the CSUGLab.

Overview: In class we discussed several possible versions of the Quicksort algorithm. These include:

1.

Using A[p] of each subproblem as the pivot.

2.

Considering the A[p], A[r], and A[(p+r)/2] elements of each subproblem and then choosing the middle one as the pivot.

3.

Switching to insertion sort for subproblems below a particular size threshold.

Your job is to implement these three versions of Quicksort and then, through testing, determine the relative performance of these algorithms as a function of input size. You will create an Array class in Java to store a user-specified number of integers, complete with various member functions for accessing and modifying array elements. You will then implement the three versions of Quicksort within a Sorter class. Finally, you will use these two components with a test harness to create and sort randomly filled Array objects of various sizes. Sorting times will be recorded and a report detailing your results will be written.

What we have done for you:

Since this is your first programming exercise, we have provided most of the code framework for you. This includes the files:

• ArrayInterface.java: This file contains a Java interface for an array-like data structure. A Java interface is used to describe class functionality. It is basically a skeletal class that lists various member functions that constitute a group of functionality. A class that implementsn interface is guaranteed to have this functionality.
• Array.java: This file contains the beginnings of an Array class. This class implements ArrayInterface. We have included the function stubs that you must complete.
• Sorter.java: This file contains the beginnings of the Sorter class. This class has function stubs for the three versions of QuickSort that you must implement, along with a stub for a partition function.
• class1.java: [NOT Tester.java as originally announced] This file contains a sample test harness for your Array and Sorter classes. This harness creates an Array object of a user specified size and then fills it with random integers. It then creates a Sorter object to sort the Array.

Code you must write

• First you must complete the Array class. This involves finishing the constructor, setElem, getElem, and getLength methods. The implementation is completely up to you.
• You must then implement the public qsort1, qsort2, and qsort3 methods of the Sorter class. These functions correspond to the three versions of QuickSort outlined at the beginning of this paper (see the various function comments for more details). You must also implement the private partition1, partition2, and partition3 methods and the public insertionSort method (again, see the various function comments). Please feel free to add any additional methods or member variables to this class that you think you may need.

The test harness that we have given you is merely an example. For this assignment, you must modify this harness to run timed trials of the three versions of QuickSort on various sized arrays. For example, you might want to modify Tester to create three randomly filled Arrays (all of the same size) and then to run the three versions of QuckSort on the arrays, timing each run and outputting the results. This is merely a suggestion the details are up to you.

For both the Array and Sorter functions, you must be sure NOT to change the names or signatures of any supplied function stubs that you complete. We will be testing your code using our own test harness, and this harness assumes that the function names/signatures are as specified. In other words, if you change the function names/signatures your code WON'T pass our tests.

What you must do:

Your job is to create a 2-3 page lab report and graph interpreting the data. Your report should be formatted appropriately. Although you do not need to follow this outline exactly, make sure you have:

• Title
• Introduction - A short summary of the experiment, why it is relevant, and what it showed.
• Experimental Procedures - Be thorough! Include at least:
  • The hardware used.
  • The software used.
  • The type of data used.
  • The number of experiments conducted.
  • The data gathered.
• Conclusions - Hypothesize why you observed the trends you did. Do not just quote numbers; interpret them. Discuss what trade-offs are probably occurring. Mention further experiments you might perform to verify your conclusions or test new hypotheses.
• Raw Data - Include the data you collected in an appendix.
• Graph - Include a plot of the data you collected in an appendix. You may use any utility that you like to generate the graph (Excel, Matlab, hand, etc.), just be sure to overlay the plots from the different QuckSort methods and label all axis.

Advice and hints:

• Start early. Get to know the Microsoft Visual J++ environment and help capabilities.
• For the Array class, you might want to look at the java.util.Vector utility class.
• Do not use large data sets until you are sure your implementation is correct.
• Think while you crunch the numbers. The goal is to do good science/engineering and discover natural patterns.

Submitting your project:

Important: Set the folder permissions so that the TA's (zlt@cs, gupta@cs, jjh14@cornell.edu, rsb11@cornell.edu, ja39@cornell.edu, prf3@cornell.edu, lc47@cornell.edu, melin@cs, welte@cs) and yourself have 'Full Control' access permission, and no one else. Drag this NetID folder onto \\Goose\courses\cs410\A1\Submissions. You will not be able to see your files, and you will only be able to submit once. Ensure your program is working before submitting it.

Grading:

• 10% coding style (neatness, comments, etc.)
• 50% correctness (10% if it compiles, 30% if it passes some of our tests, 50% if it passes all tests)
• 40% documentation (analysis, graph, grammar, etc.)