©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:
class Examples defines and runs all the tests for lists
of random integers.
class 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
same file.
class IntComp implements the Comparator for integers.
class StringComp implements the Comparator for
Strings, based on their length.
class Sorter is a wrapper that enables us to print the
timing results neatly. The file includes two implementations,
Quick and Insert. It also includes a separate but
similar class InsertList that wraps the insertion sort for
AList classes and includes two methods fillList
for first converting the List data to AList
and result that converts the sorting result saved as
AList to an ArrayList.
class Timing provides a simple way to interact with the
system clock.
class StringExamples defines and runs all the tests for lists
of random Strings.
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 List we
must compare k/2 items on average, where k is the size of the sorted
portion.
In the Algorithms class you
can see an implementation of Insertion Sort which sorts an
ArrayList<T> in-place.
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 Algorithms class.
If you try to run the Examples class you will notice there is
a RuntimeException that’s thrown. This is because there is a
missing implementation. As further practice with Comparators,
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
comparator!
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
this variable.
Now run the similar code in the class StringExamples. It
mimics the 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
Insertion and Quick Sort even on these smaller
ArrayLists.
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
Algorithms class
The fillData(...) method in the Examples
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 Example
class.
And check out the Timing for a way to query the
System for accurate time counts and what we can do with
them.
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: PieMan.java and
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.
The file 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
testing support.
Look at the definitions of the test cases and make sure you understand how the code is organized.
The interface 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 Examples
class.
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 AList class
hierarchy and add the contains method there as well.