©2008 Felleisen, Proulx, et. al.
Download the provided zip file Lab12-sorting.zip and unzip it. Create a new Eclipse project named Lab12-sorting. Add the given code to the project. You should have the following Java files:
Examples defines and runs all the tests for lists
of random integers.
Algorithms implements the imperative insertion sort and the
quicksort using the
ArrayList<T>, and the functional
insertion sort using the
AList<T> classes defined in the
IntComp implements the
Comparator for integers.
StringComp implements the
Strings, based on their length.
Sorter is a wrapper that enables us to print the
timing results neatly. The file includes two implementations,
Insert. It also includes a separate but
InsertList that wraps the insertion sort for
AList classes and includes two methods
for first converting the
List data to
result that converts the sorting result saved as
AList to an
Timing provides a simple way to interact with the
StringExamples defines and runs all the tests for lists
For this section of the lab we are going to quickly explore the differences between O(n2) and average O(n log n) sorting algorithms.
As mentioned in class, the running time of insertion sort is
approximately O((n * (n + 1))/4) = O(n2). This is because in order
to insert each element into the sorted portion of the
must compare k/2 items on average, where k is the size of the sorted
Algorithms class you
can see an implementation of Insertion Sort which sorts an
This algorithm is considered one of the best in-place sorting
algorithms because it is easy to implement and runs pretty fast. Have
a look at the implementation in the
If you try to run the
Examples class you will notice there is
RuntimeException that’s thrown. This is because there is a
missing implementation. As further practice with
you need to implement the
IntComp class which compares two
Integers using available functions.
You must then add a new instance of your class to the
Examples main method (see where the
null is?) so that the
sorting tests will work.
Once you have implemented the class and created an instance, run the
Examples class to see what it produces. Check the output
to see if it is indeed sorted... if not you will need to fix your
When the sorts work correctly, run the
Examples class again,
but this time modify the source to run 3 or 4 timed sort tests by
changing the variable loops appropriately. Note the loop which uses
Now run the similar code in the class
Examples class, but deals with lists of random
Strings. The sorting algorithms and their wrappers use
generic types and require no changes.
You should get some reasonable differences between the times of
Quick Sort even on these smaller
Sketch a plot of your results on a piece of paper and observe the difference between the slopes of the plots for the two insertion sorts and the plot for the quicksort.
Look over the interesting portions of the supplied code:
static and Generic methods in the
fillData(...) method in the
class... try to understand what’s going on there
The abstract class
Sorter and its implementations that
wrap calls to the
Algorithms code (remember the Function
Objects?) and the methods which use them in the
And check out the
Timing for a way to query the
System for accurate time counts and what we can do with
In this section you will get a chance to work with the code from yesterday’s lecture on the Visitors.
Download the provided zip file Lab12-visitors.zip and unzip
it. Create a new Eclipse
project named Lab12-visitors. Add the given code to the project. You
should have the following Java files:
ListMan.java. The file
ListMan.java contains a
similar code, but written in the contest of our standard
AList classes. You may find it easier to read that code first.
PieMan.java defines the code we covered in class
yesterday and adds test code. There are no comments
anywhere. However, the class diagram may help. Read the code and add
purpose statements to the classes and methods.
Run the program, using the
tester library for the
Look at the definitions of the test cases and make sure you understand how the code is organized.
IPieMan has a method
boolean containsTop(Object o) commented out. The purpose
is to determine whether the pie contains the given topping. Make a
list of all that you have to do to implement this method.
Make examples of the use of this method in the
Add all methods and classes needed to implement this method correctly.
If you have time left look at the implementation of the same
methods in the context of a recursively defined
hierarchy and add the
contains method there as well.