Choose 4 sorting algorithms, each with different runtime complexities (in the best, worst, or average cases). Implement each algorithm. Your code should be in C/C++. Then, write a comparative analysis of each algorithm, complete with the following information: - pseudocode of the algorithm
- explanation of how the algorithm works, intuitively
- the best, average, and worst case runtime complexity
- an explanation and/or derivation of the runtime complexity in each case--why is it O(-)?
- an explanation of what the "best" and "worst" cases are, and example data sets thereof
- charts showing the runtime of the algorithm for varying N in the best, average, and worst cases
- when would you use this algorithm? when would you avoid it?
Additionally, provide: - introduction and background sections in your report to explain the concept of sorting and why it is an important problem in computer science
- a bibliography including any references you cite
- all your code in an appendix. Make sure your code is well documented (including citations)
Your report should be printed and turned in during class. I would appreciate a PDF of your report emailed to me as well.
| 