Assignment 12 ©2011 Felleisen, Proulx, Chadwick, et. al.
Due Date: Friday, 8 April 2011 at 10:00 pm
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.
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(n2)?
Which algorithms run mostly in O(n.logn) 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.