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:- Compared the wall clock performance of several O(n log2n) sorting algorithms
- Compared the wall clock performance of O(n2) and O(n log2n) sorting algorithms
- Discovered the strengths of asymptotic analysis.
- Presented these findings in a written document.
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
- A single chart comparing the run times of all five sorts.
- A single chart comparing the comparisons used of all five sorts.
- A single chart comparing the moves used of all five sorts.
- A single chart comparing the run times of heap and quicksort
- A single chart comparing the comparisons of heap and quicksort
- A single chart comparing the moves of heap and quicksort
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:
- Introduction: provide a brief introduction to the experiment.
- Methods: describe what you did and the conditions when you did it. This includes a description of the timing framework as well as the machine on which the experiment was conducted.
- Results: present the results of your experiments, without commentary.
- Discussion: discuss what you found and draw conclusions.
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.