CPSC 170 Lab 4
As usual, create a lab4 subdirectory for today's lab, open this
document in FireFox, and start eclipse.
Sorting, Timers and Polymorphism
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.
- 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
- 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.
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.
- 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
- 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.
Notice that the first line of the class has an error. Hover over the error
to find out what the problem is.
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.
Eclipse Hint Double click on the red 'x' and eclipse will suggest
a fix to the problem.
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.
- Write a test program WeeklySales that creates an array of 10 Salesperson
objects (populated with literal data) 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.
We typically think of events as being something that the user has done,
i.e. clicking on a button, but that is not always the case.
We might also be interested in generating events at regular intervals. For
example, we might want a program that checks for new e-mail every 15 minutes.
To acheive this, we use a Timer object to generate events for us.
A timer object has an interval,
measured in milliseconds, and a listener that defines the code to be executed
after the interval of time has elapsed. (see page 470-474 or JavaDoc
for more details)
Download the files
Run the drawBars.java. Observe what
it does (be patient, there is a timer in there!)
You should have noticed that the bars changed color, one by one -- if you
didn't know better, you would expect that there was a for loop or a while loop
controlling the color change. Examine the code to find out what is really
Before you move on, you should make sure that you understand:
- How much time lapses between color changes?
- How does the timer know which bar to alter?
- How do we know that all the bars have changed color?
- What does the timer do after all the bars have changed color?
Often when we sort, especially small lists, the computer is done before we
know it (and that's a good thing). However, since we are just getting started
with sorting, it is useful to break down the sorting process to allow us
to get a better sense of what is happening.
We are going to sort the bars (according to height), using a selection sort
Instead of doing the entire sort at once, we are going to use the timer to
delay processing and see incremental steps. To achieve this you should:
- Modify bars.java to make it implement Comparable.
- In BarsPanel.java, create a method:
private int minIndex(int start) -- takes
an index start and returns the index of the
smallest bar in the list starting at index start.
- In BarsPanel.java,Create a method:
private void swap(int i, int j) -- takes
two indices and swaps the values in the list at those indices.
- Modify the refreshListener to implement a selection sort.--
At the conclusion of each timer event, you should see that
one more bar is correctly positioned. To make things easier to follow, you
should also change the color of the corectly positioned bars to blue.
Note - your final code won't be too much different than it does now, right?
Print your work to turn in.
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:
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.
- A place to enter times & compute averages.
- A place to record average times for varied array sizes
- A set of data for comparison Functions
- A blank chart titled "Random Array Sorts".
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
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!
- Printouts of your programs-
- Printouts of your programs - make sure that your name is included in the
header comments (not just written on)
- A printout of SortingCompare.sxc
- A printout of your SortCompare.xxx
- Tar the files in your lab5 directory with the command
tar czf lab4.tgz .
Please make sure that all your work is Stapled together