NAME:

LOGIN:

PRECEPT:

COS 226 Exercises on Sorting


1. [Exercise 7.2, modified] Show how the file 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 is partitioned using Program 7.2.
















2. [Exercise 8.26, modified] Draw a tree that summarizes the merges that Program 8.5 performs, for N = 11 (see Figure 8.5).











3. Give the expected number of comparisons used by Quicksort with 3-way partitioning (Program 7.5) on a file with N copies of each of two distinct keys, randomly ordered.











Extra credit. Answer the previous question for three distinct keys.