1. [30 points] Sort the array A=<5, 3, 5, 8, 5, 9, 2, 6, 9, 7, 3, 1, 4, 1> using the Quciksort

algorithm as given in the textbook (CLRS).

(a) Show what the array looks like after the PARTITION is called once.

(b) Tell whether the relative positions of any identical keys- e.g., there are three 5's -

are changed, after the PARTITION. You may want to mark the identical keys with

superscripts to differentiate them, e.g., 5ª, 3ª, 5b, 8, 5º, 9³, 2, 6, 9, 7, 3b, 1ª, 4, 1b.

(c) Draw the recursion tree. In the tree, each node, corresponding to a call to the

PARTITION, has two boxes: the first one is filled with the input size for partitioning, and

the second one is filled with number of comparisons done by the PARTITION.

(d) How many times is the PARTITION called?

(e) What is the depth of the recursion tree?

(f) How many comparisons are made?