CPS 6, Summer 1999 Random Quiz 11

Due: Wednesday, June 23, 1999 5 points

Problem 1: Quicksort (5 points)

In class we used the Quicksort algorithm to (partially) sort the sequence of numbers:

     15  3  5 21  9 64 11 30  4 17 63 49 55 29  8 38

After the first pass, we ended up with:

      8  3  5  9 11  4 15 30 64 17 63 49 55 29 21 38
                        1

with the pivot value 15 marked by a 1 below because it was the 1st pivot. Then, by recursion, we applied Quick to the left sublist and ended up with:

      4  3  5  8 11  9 15 30 64 17 63 49 55 29 21 38
               2        1

with a pivot value of 8 marked by the 2 because it was the 2nd pivot as a result of the 2nd partition step. Manually do the rest of the Quicksort, noting the order in which the pivots were found. Show the result below, by adding the missing "pivot sequence numbers" below the sorted values.

      3  4  5  8  9 11 15 17 21 29 30 38 49 55 63 64

     __ __ __  2 __ __  1 __ __ __ __ __ __ __ __ __

Note that when a sublist of length one is considered, it is bypassed by the Quick code. Assume that it is at that time designated the pivot. I.e. a list of length one is assumed to result in that element being designated the pivot.