COS 226 Exercises on Quicksort

NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Quicksort

References: Section 2.3 in Algorithms, 4th edition (Fall 2010 Preliminary Edition)

1. Suppose that the result of the shuffle in Algorithm 2.5 is P A R T I O N E D H F L. Show the result of the first call on partition() by giving the contents of the array after each exchange, as in the trace on p. 197.

2. Suppose that the result of the shuffle in Algorithm 2.5 is 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0. Show the result of the first call on partition() by giving the contents of the array after each exchange, as in the trace on p. 197. Warning: pay special attention to how the algorithm works when a key is equal to the partitioning element.