94 SORTING ALGORITHMS
3.7.3
- Trace the operation of Quicksort on the list [23, 17, 21, 3, 42, 9, 13, 1, 2,
7, 35, 4]. Show the list order and the stack of (first, last, pivot) values at the
start of every call. Count the number of comparisons and swaps that are done. - Trace the operation of Quicksort on the list [3, 9, 14, 12, 2, 17, 15, 8, 6,
18, 20, 1]. Show the list order and the stack of (first, last, pivot) values at the
start of every call. Count the number of comparisons and swaps that are done. - We showed that the Quicksort algorithm performs poorly when the list is
sorted because the pivot element is always smaller than all of the elements
left in the list. Just picking a different location of the list would have the
same problem because you could get “unlucky” and always pick the smallest
remaining value. A better alternative would be to consider three values
list[ first ], list[ last ], and list[ (first + last) / 2 ] and pick the median or mid-
dle value of these three. The comparisons to pick the middle element must
be included in the complexity analysis of the algorithm.
a. Do Question 1 using this alternative method for picking the pivot ele-
ment.
b. Do Question 2 using this alternative method for picking the pivot ele-
ment.
c. In general, how many comparisons are done in the worst case to sort a
list of N keys? (Note: You are now guaranteed to not have the smallest
value for the PivotValue, but the result can still be pretty bad.) - An alternative for the PivotList algorithm would be to have two indices
into the list. The first moves up from the bottom and the other moves down
from the top. The main loop of the algorithm will advance the lower index
until a value greater than the PivotValue is found, and the upper index is
moved until a value less than the PivotValue is found. Then these two are
swapped. This process repeats until the two indices cross. These inner loops
are very fast because the overhead of checking for the end of the list is elim-
inated, but the problem is that they will do an extra swap when the indices
pass each other. So, the algorithm does one extra swap to correct this. The
full algorithm is
PivotList( list, first, last )
list the elements to work with
first the index of the first element
last the index of the last element
■3.7.3 EXERCISES