Quicksort. 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 left_partition cab dad ebb 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=10+1; i & x) { qsort(x, 0, x.size()-1); 1. 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: lo=0 add 1 bed 2 ace hi=3 baa 4 bee bee 5 cab cab 6 dad dad 7 ebb ebb start of iter i = 1 start of iter i = 2 start of iter i = 3 end of iter i = 3 after swap(x [lo],x[p]) bee cab dad ebb bee cab dad ebb bee cab dad ebb 2. Complete the following loop invariant by providing the range of indices for which the state- ment 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], which part of the invariant at iteration i +1 is the same as at iteration i, (A) or (B)? 4. 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. 5. 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. Quicksort. 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 left_partition cab dad ebb 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=10+1; i & x) { qsort(x, 0, x.size()-1); 1. 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: lo=0 add 1 bed 2 ace hi=3 baa 4 bee bee 5 cab cab 6 dad dad 7 ebb ebb start of iter i = 1 start of iter i = 2 start of iter i = 3 end of iter i = 3 after swap(x [lo],x[p]) bee cab dad ebb bee cab dad ebb bee cab dad ebb 2. Complete the following loop invariant by providing the range of indices for which the state- ment 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], which part of the invariant at iteration i +1 is the same as at iteration i, (A) or (B)? 4. 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. 5. 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