Question -Objective: The objective of this homework is familiarize you with the performance characteristics of Quick sort under normal and worst case conditions. The assignment will require some programming and interpretation of the results.
Assignment: Using the pseudo code provided in the Cormen text for Quick sort, implement a working program that uses Quick sort 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 propose that your program be implemented in c, or c++, so that you can use debugging tools, such as gdb and ddd, if necessary.
Case 1- 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.
Case 2- 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.
Answer this question and show each and every step with example.