3. Dual-pivot Quicksort. In class, we looked at the randomized version of quicksort algorithm where we choose the pivot uniformly at random (i.e. an element in an n-element array is chosen to be the pivot with probability 1). Consider a variant of the randomized quicksort algorithm where instead of choosing one pivot uiformly at random, we would instead choose tuo pivots 2 1 and 22 uniformly at random (we call this dual-pivot quicksort') We then partition the array around these two pivots in the following way: 1st Pivot 2nd Pivot and sr2 (a) (4 points) What would be the recurrence and running time of the algorithm if we always choose the 1st pivot to be the minimum element and the 2nd pivot to be the maximum element (i.e. the worst-case input and random choices)? (b) (4 points) What would be the recurrence and running time of the algorithm if we always choose the two pivots such that the array would be partitioned into three equally-sized sub-arrays (i.e. the best-case input and random choices)? (c) (2 points) As is the case with the single-pot quicksort algorithm, we can prove that the expected running time of dual-pivot quicksort is (n lg n). Explain in your own words what we mean by expected running time (i.e, what kind of inputs is this analysis escribing?) 3. Dual-pivot Quicksort. In class, we looked at the randomized version of quicksort algorithm where we choose the pivot uniformly at random (i.e. an element in an n-element array is chosen to be the pivot with probability 1). Consider a variant of the randomized quicksort algorithm where instead of choosing one pivot uiformly at random, we would instead choose tuo pivots 2 1 and 22 uniformly at random (we call this dual-pivot quicksort') We then partition the array around these two pivots in the following way: 1st Pivot 2nd Pivot and sr2 (a) (4 points) What would be the recurrence and running time of the algorithm if we always choose the 1st pivot to be the minimum element and the 2nd pivot to be the maximum element (i.e. the worst-case input and random choices)? (b) (4 points) What would be the recurrence and running time of the algorithm if we always choose the two pivots such that the array would be partitioned into three equally-sized sub-arrays (i.e. the best-case input and random choices)? (c) (2 points) As is the case with the single-pot quicksort algorithm, we can prove that the expected running time of dual-pivot quicksort is (n lg n). Explain in your own words what we mean by expected running time (i.e, what kind of inputs is this analysis escribing?)
