(10 pts) Using Figure 7.1 of CLRS (Page 41, lecture slides for Chapter 7) as a model, illustrate the operation of the Partition procedure as given in lecture (Page 40, lecture slides for Chapter 7) on the array . Assume that the last element of the array is selected as the pivot element. Indicate values of i and j after each step.

i pj (an) p.i j pi j (d 01) (g) 2 2 1 3 8 75 64 (b) 21387 56 4 Figure 7.1 The operation of PARTITION on a sample array. Lightly shaded array elements are all in the first partition with values no greater than x. Heavily shaded elements are in the second partition with values greater than x. The unshaded elements have not yet been put in one of the first two partitions, and the final white element is the pivot. (a) The initial array and variable settings. None of the elements have been placed in either of the first two partitions. (b) The value 2 is "swapped with itself" and put in the partition of smaller values. (c)-d) The values 8 and 7 are added to the partition of larger values. (e) The values 1 and 8 are swapped, and the smaller partition grows. ( The values 3 and 7 are swapped, and the smaller partition grows. (g)-(h) The larger partition grows to include 5 and 6 and the loop terminates. (i) In lines 7-8, the pivot element is swapped so that it lies between the two partitions