Write a program in C++ to test the performance of quick select algorithm (L12 slide 7-9) under different group size setting. In the slides, to find the pivot, the algorithm divide all elements into group of 5, find the median of each group and use the median of medians from all group as pivot. In our assignment 4 we studied the analysis of using group of 3 and group of 7. Now you are writing a program to count the operations in all these setting (even more, your program can take any setting of group size that is greater than 2 and less than n)

Input to the program:

1. Size of each group in pivot selection (at least 3, at most n)

2. Number of elements in the sequence

3. k (kth number looking for in the selection problem)

The program needs to randomly generate integer values as elements in the sequence, run the algorithm, count the number of operations and output following

1. kth element''s value

2. number of operations performed

Use the program to collect the performance of group size = 3, 5, 7 under different input size and plot them in one chart. Explain the chart in a report.

Turn in your report and program source code.

Due date: Dec. 2nd Friday midnight

Hint: 1. Start with Random Select, (textbook 9.2 and 7.3)

2. modify it to group of 5 version quick select, (textbook 9.3)

3. modify group of 5 to group of 3,

4. modify to group of 7,

5. collect the data and prepare the report,

6. modify the code to accept any group size