4. Quicksort (20 points). In practice, quicksort is one of the fastest sorting algorithms. 1. Pick a pivot (e.g. the first element) bee bed cab ace dad baa add ebb 2. Reorder the array such that all elements pivot are to its right. add bed ace baa bee cab dad cbb left-partition right-partition 3. Recursively sort each partition. void qsort (vector &x, int lo, int hi) { if (lo >= hi) return; int p = lo; for(int i=lo+1; i & x) { qsort(x, 0, x.size()-1); (a) (4 points) Show the contents of the array x at the start of each iteration of the for-loop, after the for-loop, and after the swap, in the call qsort(x, 0, 3) on the input shown below: bec lo=0 i 2 hi=3 4 5 6 7 start of iter i=1 add bed ace baa bee cab dad cbb start of iter i = 2 bee cab dadebb start of iter i = 3 cab dad cbb end of iter i = 3 bee cab dadebb after swap(x[lo],x[p]) bee cab dadebb (b) (4 points) Complete the following loop invariant by providing the range of indices for which the statement is true. Note that x[a ... b] is empty if a > b. At the start of iteration i of the for-loop in qsort: (A) x[ _] x[lo] (c) (4 points) To prove the loop invariant, we use induction on the iteration index i. In the base case, when i=lo+1 and prlo, the ranges for parts (A) and (B) are empty and the invariant is trivially true. For the inductive step going from iteration i to ite i'=i+1: i. If x[i] = x[lo], which part of the invariant at iteration i +1 is the same as at iteration i, (A) or (B)? (d) (4 points) What is the worst case running time of Quicksort on inputs of size n? First, show the recurrence relation representing the running time for a worst case input. Then give the asymptotic result. (e) (4 points) Suppose in every recursive call to sort a subarray, we choose a pivot, in time proportional to the size of the subarrary, that is never one of the smallest 1/4 or largest 1/4 elements. What is the worst case running time of Quicksort on inputs of size n in this case? Give the recurrence and the asymptotic closed form