Let A[1 9] = 4, 3, 7, 5, 9, 8, 6, 2, 0. Illustrate the execution of Randomized-Select(A, 1, 9, 4) with Randomized-Partition replaced with Partition; see pg 216. More precisely, list all calls to Randomized-Select (A, p, r, i) with p, r, i specied. Also state A[1 9] just before each call to Randomized-Select.

216 Chapter 9 Medians and Order Statistics RANDOMIZED-SELECT uses the procedure RANDOMIZED-PARTITION intro- duced in Section 7.3. Thus, like RANDOMIZED-QUICKSORT, it is a randomized al- gorithm, since its behavior is determined in part by the output of a random-number generator. The following code for RANDOMIZED-SELECT returns the ith smallest element of the array A[p.. r]. RANDOMIZED-SELECT (A, p, r, i) 1 if p r return A[p] 3 RANDOMIZED-PARTITION (A, p, r) 4 k 5 if i k ll the pivot value is the answer return A[q] 7 else if i