NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Quicksort

References: Section 2.3 in Algorithms 4/e


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. 291.





















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. 291. Warning: pay special attention to how the algorithm works when an item is equal to the partitioning item.