1. Show the partition result of this input array.

Index	0	1	2	3	4	5	6	7	8	9
Input	342	773	429	966	19	952	711	133	684	143
Partition Result

2.Given 10 integers from 1 to 10, provide 5 permutations that each of them results in worst case running time for quick sort, which means each call to partition method can only reduce the array size by 1.

3.Suppose that we scan over items with keys equal to the partitioning items key instead of stopping the scans when we encounter them. With this change, what is the running time for this Quick Sort implementation given input with all equal keys?

4.QuickSortRandomized uses two methods to do quick sort. The first method shuffles the input array before doing regular quick sort. The second method randomly picks a pivot element during each partition. Run QuickSortRandomizedTest five times and provide the results in the following table. From your experiments, which method runs faster?

N	Average Method1 Duration	Average Method 2 Duration
1000
10000
100000
1000000
10000000