©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

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

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:

Which algorithms run mostly in quadratic time, i.e. *O*(*n*^{2})?

Which algorithms run mostly in *O*(*n*.*l**o**g*_{n}) time?

Which algorithms use the functional style, using `Cons`
lists?

Which algorithm is the *selection sort*?

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

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.

Last modified: Thursday, April 1st, 2010 1:31:15pm