Implement the various sorting algorithms we have discussed
in class for lists of integers. Then, you will measure how much CPU time each algorithm takes
for arrays of varying sizes and construct a report comparing and contrasting each algorithm and
discussing how real-world performance mirrors (or not) theoretical performance.
Algorithms to implement
• Bubble – Section 3.1
• Selection – Section 3.1
• Insertion – Section 4.1
• Merge – Section 5.1
• Quick (use 1st element as pivot) – Section 5.2
• Heap – Section 6.4. You must implement your own Heap data structure. Use the topdown method discussed in class to build the heap.
• Counting – Section 7.1
Driver (Main Program): Your main program will generate integer arrays of size 5, 10, 50, 100,
200, 400, 800, 1600, 2400 (or the maximum size your computer will allow) and execute the
sorting algorithms on each of the arrays. You will need to use functions to measure executiontime of each call to each algorithm on each array.
You are allowed to use any programming language of your choice for this assignment. You must
document your code.
With the timing information you collect from your program, write a 2-page, double-spaced
report describing the results. The following are questions (not an exhaustive list) to consider:
• If I plot the time for a specific algorithm, does the curve look like similar to the function
of the asymptotic class?
• How large must the arrays before algorithms such as MergeSort and QuickSort are
faster than Bubble/Selection/Insertion sort?
• Are there algorithms that have similar timing curves?