Use Figure 7.1 as a model, illustrate the operation of PARTITION (A, 1, 6) on the array A = . Show all intermediate steps how the array is transformed.

(a) i pi 2871356 pi (b) pi 2 (c) 713564 pi 2 871 3564 (e) 2178 P 2138756 P i (g) P (h) 213756 () Figure 7.1 The operation of PARTITION on a sample array, Array entry A[r] becomes the pivot clement x. 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 el- ements have not yet been put in one of the first two partitions, and the final white element is the pivot x. (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. (ed) 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.) In lines 7-8, the pivot element is swapped so that it lies between the two partitions. (a) i pi 2871356 pi (b) pi 2 (c) 713564 pi 2 871 3564 (e) 2178 P 2138756 P i (g) P (h) 213756 () Figure 7.1 The operation of PARTITION on a sample array, Array entry A[r] becomes the pivot clement x. 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 el- ements have not yet been put in one of the first two partitions, and the final white element is the pivot x. (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. (ed) 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.) In lines 7-8, the pivot element is swapped so that it lies between the two partitions