©2010 Felleisen, Proulx, et. al.

11  Heapsort; StressTests

Portfolio Programs: The Java Collections Framework

Read through the documentation for Java Collections Framework library. Find how you can run the sorting algorithms defined there. Write a simple program that will test these algorithms and measure their timing in a manner similar to the last two labs.

11.1  Priority Queue

1. Implement the heap-based priority queue algorithm as described in part 2 of Lab 11.

2. Now implement a simple variant of heapstort as follows:

   • In the first step insert the given data into your PriorityQueue, one item at a time.

   • In the second step, remove the data from your PriorityQueue and insert them into the resulting ArrayList, one at a time.

     If you just add each item at the end, you will end up with a list ordered in descending order. If you wish to get the correct ordering, insert each item at the index 0.

11.2  Stress Tests

For this problem finish the work on the first problem in Lab 11, especially focusing on the set of questions and the answers you may find by running the timing tests.

Part 1

Add your implementation of the heapsort to the sorting algorithms that will be measured. The skeleton for this is already in place.

Part 2

Run the program a few times with small data sizes, to get familiar with what it can do. Then run experiments and try to answer the following questions:

1. Which algorithms run mostly in quadratic time, i.e. O(n²)?

2. Which algorithms run mostly in O(n.log_n) time?

3. Which algorithms use the functional style, using Cons lists?

4. Which algorithm is the selection sort?

5. Why is there a difference when the algorithms use a different Comparator?

6. Copy the results into a spreadsheet. You may save the result portion in a text editor with a .csv suffix and open it in Excel (or some other spreadsheet of your choice). You can now study the data and represent the results as charts. Do so for at least three algorithms, where there is one of each — a quadratic algorithm and a linear-logarithmic algorithm.

   Produce a report with a paragraph that explains what you learned, using the Excel charts to illustrate this.

   Your report should have a professional look – typed, computer generated charts, reasonably organized. It does not have to be more than 2 pages long, one page is OK.