CPSC 170 Lab 6
Polymorphic Sorting and Timings

As usual, create a lab6 subdirectory for today's lab, open this document in FireFox, and start emacs.

Polymorphic Sorting

File Sorting.java contains the Sorting class from Listing 9.9 in the text. This class implements both the selection sort and the insertion sort algorithms for sorting any array of Comparable objects in ascending order.

  1. File Strings.java contains a program to read in an array of Strings, then invoke the selection sort algorithm on them, then print the sorted array. Run this program to see how it works.

  2. Suppose you want to sort integers instead of strings. You could just copy Strings.java into a new program Numbers.java and change type String to type int everywhere. Try this; what happens when you compile it? Be sure you understand the problem.

  3. Remember wrapper classes from CS120? We used these whene we wanted an object that held a primitive data type. Java 1.5 has a feature called autoboxing that does automatic type conversion between primitive types and their corresponding object ("wrapper") types. Autoboxing is briefly explained on p. 139 of the text. Note that every primitive type (int, double, boolean, etc) has a corresponding wrapper class (Integer, Double, Boolean, etc) that it will automatically convert back and forth with.

  4. Modify Numbers.java so that it takes advantage of the autoboxing feature to read in integers from the user and use the sorting methods in Sorting.java to sort them. Note that no changes are necessary to Sorting.java, and only very small changes are needed in Numbers.java.

  5. File Salesperson.java partially defines a class that represents a sales person. This is very similar to the Contact class in listing 9.10. However, a sales person has a first name, last name, and a total number of sales (an int) rather than a first name, last name, and phone number. Notice that the class header indicates that Salesperson implements Comparable.

    Compile Salesperson.java and see what you get.

    Just because we say it implements Comparable doesn't make it so! We need to define what it means to compare two Salespersons by writing a compareTo method for the Salesperson class. The comparison should be based on total sales; that is, return a negative number if the executing object has total sales less than the other object and return a positive number if the sales are greater. Use the name of the sales person to break a tie (alphabetical order, last name then first name); if the sales and the names are the same, return 0.

  6. Write a test program WeeklySales that creates an array of 10 Salesperson objects and uses insertion sort to sort it. In your output the sales staff should be listed in order of sales from least to most with people having the same number of sales in alphabetical order.

    Choose the data for your test case wisely!

    Be sure to include data that will verify that your program works in all conditions. Included comments in your program that justifies your data set.

Timing Sorting Algorithms

File TimeSorts.java contains a menu-driven program that lets the user create, randomly fill, display and sort any size array of integers using either selection sort or insertion sort as defined in the Sorting class. Save this file to your directory and run it a few times to see how it works. Note that you have to fill an array before you can run it -- otherwise you get a NullPtrException, as it is trying to sort an array of null objects.

Now you will use this program to examine the runtimes of insertion sort and selection sort. You can do this using the java method long System.currentTimeMillis(), which returns the current system time in milliseconds. (Note that it returns a long, not an int.) In TimeSorts, just get the system time immediately before and immediately after you perform either of the sorts. Then subtract the first from the second, and you have the time required for the operation in milliseconds.

Note that the first couple of times you run a method you might get longer runtimes as it loads the code for that method. Ignore these times and use the "steady-state" times you get on subsequent runs. You will be collecting a series of times on arrays of different sizes to get a sense of how these sorting algorithms work.

Download the file SortingCompare.sxc to your directory. This is an spreadsheet file that can be used with OpenOffice. Go to the Applications menu (on the desktop), select Office -> OpenOffice Spreadsheet. When the application has launched you can open the file using File->open When you open the file, you should see 4 major sections in the spreadsheet:

  1. A place to enter times & compute averages.
  2. A place to record average times for varied array sizes
  3. A set of data for comparison Functions
  4. A blank chart titled "Random Array Sorts".
Get and record four steady-state times for the selection sort on an array with 1000 elements Make sure that you remember to randomize the array before each sort (option 3) - we don't want to sort an array that is already in order (yet). You will notice that the average of these times is automatically computed for you. Once you have collected four times, type the average value into the corresponding cell under "Sort Performance". You should see the value appear in the chart on the side.

Complete the "Sort Performance" table by repeatedly running TimeSorts with the appropriate sorting algorithm and arraysize. When the table is complete, you should see a graph of the sort performance in the "Random Array Sorts" chart. Now is a good time to save this file.

Create a new data file called "SortCompare.xxx" where "xxx" are your initials. In this file write an explanation of the sort performance in terms of the algorithm complexity. Discuss how the execution time changes for different array sizes using the same algorithm and how the execution time changes for the same array size using different algorithms. To help with your discussion, it is useful to compare the algorithm's performance against a generic function. To see this visually in the chart, you can copy (one at a time) the comparison functions (n, n^2, and n^3) to the column next to the Sort Performance table (column D). How does the growth of these functions compare to the growth of the algorithm?

Next we want to compare how these algorithms perform on a list that is already sorted (Do you think there will be a difference?) In the spreadsheet, click on the "Sorted Arrays" tab, to get a new sheet that will allow you to record this data. It should look identical to the previous sheet, but without your data.

To fill this out, you will collect data the same way as before, except don't randomize the lists between sorts and don't record the first sort (it will be the time for an unsorted array). When the Sort Performance table is completely filled out, analyze the results and record your findings in "SortCompare.xxx". You should have found a significant difference between the algorithm's performance - justify why this is the case - think carefully about how you should characterize the performance of the insertion sort on a sorted list -- is it constant? Try some timing some array sizes that are very large until you can answer this question.

Don't forget to save the spreadsheet file before closing!

HAND IN: