Fri, March 18th by 11:59pm Late assignments will be penalized 20% per day.
Empirical Sorting Comparison
The purpose of this assignment is to compare the various sorting algorithms implemented in assignments 1, 2, and 3.
Submission
The submission for this assignment should consist of a written report that graphically shows the results for all five sorts and provides a discussion of what was observed. DO NOT include your completed source code, but provide tables of numerical data in an appendix at the end of the report.
The report should include meaningful plots (e.g. using Excel) of all the data showing important comparison characteristics. There should be a summary table listing the sort method, asymptotic behavior, and empirical asymptotic formula with “best-fit” constants.
DISCUSS the results in terms of observed behavior (e.g. how well does the asymptotic behavior match the empirical data), comparison of behaviors between sorts (e.g. which ones perform better at which data set sizes), comparison of hidden constants for sorts with the same asymptotic behaviors, and any other important observed features. The discussion should refer to the graphs when appropriate to illustrate each aspect. Some questions that should be answered with graphs and brief textual explanations include:
- Does the empirical constant vary for each sort based on element range? Briefly explain why/why not?
- How well does the empirical data for each sort fit the asymptotic trend curve, particularly for small data sets? Show a graph with the empirical data and trend curves for all sorts.
- Which sorts have the best runtime for small data sets, i.e. small n, for the small element range? Show a graph with the empirical data for all sorts.
- Which sorts have the best runtime for small data sets, i.e. small n, for the large element range? Show a graph with the empirical data for all sorts.
- Which sorts have the best runtime for large data sets, i.e. large n, for the small element range? Show a graph with the empirical data for all sorts.
- Which sorts have the best runtime for large data sets, i.e. large n, for the large element range? Show a graph with the empirical data for all sorts.
- How do the n lg n sorts compare to each other for the small element ranges both in terms of runtime and memory usage?
- How do the n lg n sorts compare to each other for the large element ranges both in terms of runtime and memory usage?
SUMMARIZE the results by describing under what conditions you would select which sort, i.e. if you were asked to sort a data set, what criteria would you use in making your selection?
Grading
- Behavior based on range - 10%
- Asymptotic fit for small n - 10%
- Comparison for small range, small n - 10%
- Comparison for large range, small n - 10%*
- Comparison for small range, large n - 10%*
- Comparison for large range, large n - 10%*
- Comparison for n lg n, small range - 5%
- Comparison for n lg n, large range - 5%
- Summary - 10%
- Table of asymptotic constants - 5%
- Table of empirical data - 3%
- Writing quality - 12%
Upload a .pdf file to Canvas by Friday, March 18 at 11:59pm
