Homework 4, O(n log2n) Sort Comparison.

Short Description:

Perform a wall clock timing analysis of several O(n log2n) sorts, describe the results and discuss the strengths of asymptotic analysis.

Goals

When you finish this homework, you should have:

Formal Description

Using the framework from the alternative activity, compare the wall clock performance of heap sort, quick sort and the sorts from homework 3. Present graphical representation of these results and summarize your experiment.

Implement, debug and test the performance of heap sort and quicksort.

After you have implemented these algorithms, perform a series of timing experiments, counting the number of comparisons, data moves and total time spent in each sort. You should sort between 1,000 and 10,000 elements that have been randomly generated on the range [0 to 1,000,000] ten times each.

After this, you will probably want to test the implementations of these two new sorts on a much larger number of inputs to have meaningful results.

Produce several tables showing the summary of your results. This should include your five sorts tests. This should present average comparisons, moves and times for each sort.

Produce as second version of this table for the extended testing of heap and quicksort.

Generate

Make sure that your graphs are well labeled and clearly present the results.

Write a report describing your findings and interpreting the results. Your report should follow the IMRD format:

Make sure that you include a discussion of the difference between asymptotic time and wall clock time in measuring performance. Does each have a purpose?

Notes:

As always you must credit any collaborators, including AI and describe the amount of AI used in completing this homework.

If you wish to test any other versions of O(n log2n ) sorts, please do so and include your results in your final report.

Required Files

A single document containing your data and results.

Submission

Submit the assignment to the D2L folder Homework 4 by the due date.