**Assignment 12** ©2011 Felleisen, Proulx, Chadwick, et. al.

# Heapsort; StressTests

**Due Date: Friday, 8 April 2011 at 10:00 pm**

# 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.

# Pair Programming Assignment

## 11.1 Stress Tests

Finish the work on Lab 12,
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? Explain how did you come to that conclusion.

Which algorithm is the *selection sort*? Justify your answer

Why is there a difference when the algorithms use a different
`Comparator`? Where do you see this difference most
prominently and why?

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: Monday, April 4th, 2011 9:10:56pm