Program Assignment #1
In this program you will implement a hybrid sorting algorithm called
PickBestSort. This sorting algorithm makes a single pass through the data
to analyze its features, and based on the analysis calls one of the following
sort routines:
* Insertion Sort
* Merge Sort
* Heap Sort
* Counting Sort
* Bucket Sort
Your analysis routine should be designed to maximize the total efficiency
of the algorithm and should run in time O(n). If your analysis reveals that
the input array is almost already sorted, for example, then Insertion Sort
would be the best choice. Input to your program should consist of a file
containing the number of items to be sorted on the first line, followed
by the actual integer values to be sorted, one integer per line. Your
output should include the original and sorted sequences as well as the run
time of the entire program (analysis time, sort time, and total run time).
Your program score will be graded based on the following criteria:
* Implementation of Insertion Sort 10 points
* Implementation of Merge Sort 15 points
* Implementation of Heap Sort 15 points
* Implementation of Counting Sort 15 points
* Implementation of Bucket Sort 15 points
* Design of analysis routine 20 points
* Quality of code and comments 10 points
You may not borrow code written by a fellow student in this class or
provided online. That would be cheating. If you have questions about the
program, contact the TA by email or in person during office hours.
Turn in your program by emailing a single zip file containing the code,
directions for compiling and running, and sample output directly to the TA
by midnight on the due date. Your program can be written in any language,
but should be able to run on omega using the compile and execution
instructions you provide. Late submissions will not be accepted.
Have fun!