Suppose in quicksort, we have access to an algorithm which chooses a pivot such that, the ratio of the size of the two subarrays divided by the pivot is a constant k.
computer science
Description
. (16 pts) Suppose in quicksort, we have access to an algorithm which chooses a pivot such that, the ratio of the size of the two subarrays divided by the pivot is a constant k. i.e an array of size n is divided into two arrays, the first array is of size n1 = nk k+1 and the second array is of size n2 = n k+1 so that the ratio n1 n2 = k a constant. (a) (3 pts) Given an array, what value of k will result in the best partitioning? (b) (10 pts) Write down a recurrence relation for this version of QuickSort, and solve it asymptotically using recursion tree method to come up with a big-O notation. For this part of the question assume k = 3. Show your work, write down the first few levels of the tree, identify the pattern and solve. Assume that the time it takes to find the pivot is Θ(n) for lists of length n. Note: Remember that a big-O bound is just an upper bound. So come up with an expression and make arguments based on the big-O notation definition. (c) (3 pts) Does the value of k affect the running time?
Instruction Files
Q.pdf
270.8 KB
