Question

3 Quicksort 10 points (5 points each) 1. Suppose that you are given an array A[1..n] and that you want to sort it using quicksort. Further suppose that your algorithm could consult an oracle to predict what element to use as the pivot. Which element would it pick so that your algorithm would run as fast as possible? What is the running time given your pivot? 2. Run the partition algorithm to partition the array A (6,7,2,4, 10,8, 1,9)

Answer 1

1. Quicksort will run fastest, when every time pivot element selected to partition the array has rank n/2 where n is the elements in the array whose pivot is selected. Hence oracle will return the element of rank n/2 as the pivot element.

If this happens, then array will be partitioned equally after each recursion and hence time complexity will be given by

T(n) = 2T(n/2) + O(n)

which solves to T(n) = O(n log n)

2. Given array A = {6,7,2,4,10,8,1,9} consisting of 8 elements, so the best pivot element to partition will be 6 since it has rank 4 in the sorted array.

Hence the element 6 will partition the array A as

2,4,1, 6, 7,10,8,9

Then in the left subarray, element 2 will be pivot and in right subarray element 8 will be pivot and the result will be

1, 2, 4, 6, 7, 8, 10,9

Here the rightmost subarray of 2 elements are not sorted and hence element 9 will be selected as pivot which will finally sort the array as

1,2,4,6,7,8,9,10

Please comment for any clarification.