©2010 Felleisen, Proulx, et. al.

10  Stress Tests; Priority Queue; Heapsort

10.1  StressTests - Timing Tests

Your job is now to be an algorithm detective. The program we give you allows you to run any of the six different sorting algorithms on data sets of five different sizes using three different Comparators to define the ordering of the data. When you run the program, the time that each of these algorithms took to complete the task is shown in the console.

To run the program you need to do the following:


Spend about fifteen minutes trying to answer some of the following questions. Finish the work as a part of the Assignment 10.

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(n2)?

  2. Which algorithms run mostly in O(n.logn) 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.

Priority Queue: Heap and Heapsort

Our first goal in this section is to design a priority queue using the heap algorithm. We then use this to implement the heapsort algorithm and add it to our collection of algorithms to be evaluated.

Recall the properties of the Heap from yesterday’s lecture:

If it helps you, draw the picture of the tree and manipulate stickies or pieces of paper to see how the algorithms for insertion and deletion of nodes work.

Typically, we represent this heap as an ArrayList with the first item (at index 0) unused (maybe null).

Last modified: Monday, November 8th, 2010 4:55:12pm