Project Bonus辅导、讲解PS/Python程序语言、辅导Python设计、讲解Quicksort留学生

Project Bonus:

Goal:Empirical study to compare running times of different Quicksort optimization strategies

Task:Starting with the code for Quicksort given in chapter 7, write a series of Quicksort implementations to test the following optimizations on a wide range of input data sizes N. Try these optimizations in various combinations to try and develop the fastest possible Quicksort implementation that you can.

(a) Look at more values when selecting a pivot.

(b) Do not make a recursive call to qsort when the list size falls below a given threshold, and use Insertion Sort to complete the sorting process. Test various values for the threshold size.

(c) Eliminate recursion by using a stack.

In your main program, first you can generate N different random values to be sorted. It then executes Quicksort in different ways: no optimizations, with optimization (a) or (b) or (c) or their various combinations (such as (a) combine (b), (a) combine (c), (b) combine (c), (a) combine (b) and (c)). It writes out N, optimization strategy, and the running time. It repeats this for N = 10, 100, 1000, 10000, 100000, 1000000.

Please ensure that you generate really random number. You’d better using an appropriate ‘seed’: this is used to initialize the random number generation process.

Deliverables: Your instructor will view the output of your program. In your report, you should present a graph by doing following: Run the program four times for each optimization strategy, and average the running time for each value of N across the four runs and graph the average values. In the graph, the x-axis is N and the Y-axis is the average running time. Plot the points for different optimization strategy.