For this assignment, you will implement several sorting algorithms and collect data on their running times. I want you to turn in your source code and a type-written report. Your report should include the questions you are trying to answer, a discussion and justification of your data-collection strategy, your data (presented in whatever forms you feel appropriate, including tabular and/or graphical forms), and your interpretation of the data. In particular, you should discuss the extent to which your data agree with the predictions of the theory presented in Chapter 2 of our textbook.
Choose one of the following topics.
Don't just try to answer my list of questions (generated as it was off the top of my head late at night). Try to write code and collect data that will help you understand sorting for small values of N, and report your findings.
For this project, you should implement at least three sorting algorithms. I'd do Quicksort, Mergesort, and Insertion Sort for starters, but that's me. Make your own choices.
What I want you to do if you choose to study large N's is implement at least three algorithms, including Radix sort and one of the NlgN sorts (Quick, Merge, or Heap). Collect timing data in whatever fashion you deem appropriate, but make sure to include data reflecting the effects of platform choice and compiler optimization. The -O flag for the Unix C/C++ compilers turns on optimization. We have gnu C compilers on Intel systems (Pentium and 486 in CMC 306, Pentium Pro in several faculty offices), on MIPS systems (the SGI's in CMC 307), and on Motorola 68040 systems (the black NeXTs).
void Sort( int *key, int N ), or void Sort( short *key, int N ),where the array key[] contains the integers to be sorted, and N is the number of integers to be sorted. I recommend short integers because they are implemented as two-byte quantities on all of our department's platforms, so you won't have to worry about whether your data are being messed up by the difference between 16-bit and 32-bit integers.
By keeping a consistent interface, you'll simplify your data-collection code, and you'll factor out function-calling overhead from some of your comparisons between algorithms (though, of course, function-calling overhead is a real difference between recursive and non-recursive algorithms). If you want to modify the interface, go ahead, but I recommend keeping it simple.
Turn in your code using HSP. Put your sorting routines in a file named sorts.c (or sorts.cc) and your main() and data-collection code in a file named sortmain.c.
Do your best, but don't consider the open-endedness of this assignment to be a mandate for exhaustive 50-page reports. State your questions, present your data, draw your conclusions, and be done with it. The evaluation of implemented algorithms is hard stuff. This is an opportunity for you to get introduced to it.
If you can, please print your reports 2-up.
Start early, have fun, and keep in touch.