Project 1: Analysis of Sorting Algorithms

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.