©2008 Felleisen, Proulx, et. al.

Algorithm Complexity: Stress Tests

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:

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.

Insertion Sort:

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.

Quick Sort:

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.

Your Task

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:


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.

Last modified: Tuesday, April 1st, 2008 7:52:08am