CPSC 170 Lab 4
Polymorphic Sorting and Timings

Polymorphic Sorting

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. Java 1.5 has a new feature called autoboxing that does automatic type conversion between primitive types and their corresponding object ("wrapper") types. Autoboxing is briefly explained on p. 141 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. Write 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. Be sure to write your test program so that it tests all interesting cases!

Timing Sorting Algorithms

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.

Add appropriate calls to System.currentTimeMillis() to your program and fill out the tables below. Get and record at least 5 steady-state times for each entry, then average them and circle the average. Note that once an array is sorted you can use it for the "sorted array" columns, but you'll have to keep refilling it with random elements to get new times for the "random array" columns.

You'll find that you get useful times for the first three columns, but not for the last one. Why not? Time insertion sort on a sorted array for additional array sizes of your choosing until you have at least four useful sets of data.

On a separate sheet, explain the times you see in terms of the known complexities of the algorithms. Discuss both the times for different array sizes for each algorithm (i.e., the columns) and the times for different algorithms for each array size (i.e., the rows).