Objective: familiarize  with the performance characteristics of Quicksort under normal and worst case conditions. The assignment will require some programming and interpretation of the results.

Assignment: Using the pseudocode provided in the Cormen text for Quicksort, implement a working program that uses Quicksort to sort the elements in an array. In order to make meaningful comparisons, your array should be fairly large. (Try n=10,000 and see if you observe measurable changes in performance. You might also try a larger array if the time measurements do not vary significantly.) Do not use the library function, as it may include features that will prevent you from observing the differences between expected and worst case performance.

I suggest that your program be implemented in c, or c++, so that you can use debugging tools, such as gdb and ddd, if necessary.

Part I

Generate a main program which initializes your data array to be sorted - be careful with your array index numbers. You can use a random number generator to generate entries for the array. Then, call your Quicksort routine and sort the array while you measure the elapsed time. In the same program, using the sorted array as an input, call your Quicksort routine and again measure the elapsed time.

Part II

Modify your code to use a randomized selection of the pivot value as shown in the Randomized Quicksort pseudocode and rerun the experiment. Again, measure the execution times of sorting unsorted and already sorted arrays.