Source code online books for professionals by professionals

SeLeCtING IN LINear tIMe, GUaraNteeD!
the selection algorithm implemented in this section is known as randomized select (although the randomized 
version usually chooses the pivot more randomly than here; see exercise 6-13). it lets you do selection (for 
example, find the median) in linear expected time, but if the pivot choices are poor at each step, you end up with 
the handshake recurrence (linear work, but reducing size by only 1) and thereby quadratic running time. While 
such an extreme result is unlikely in practice (though, again, see exercise 6-13), you can in fact avoid it also in 
the worst case.
it turns out guaranteeing that the pivot is even a small percentage into the sequence (that is, not at either end, or 
a constant number of steps from it) is enough for the running time to be linear. in 1973, a group of algorists (blum, 
Floyd, pratt, rivest, and tarjan) came up with a version of the algorithm that gives exactly this kind of guarantee.
the algorithm is a bit involved, but the core idea is simple enough: First divide the sequence into groups of five, 
or some other small constant. Find the median in each, using, for example, a simple sorting algorithm. So far, 
we’ve used only linear time. now, find the median among these medians, using the linear selection algorithm 
recursively. this will work, because the number of medians is smaller than the size of the original sequence—still 
a bit mind-bending. the resulting value is a pivot that is guaranteed to be good enough to avoid the degenerate 
recursion—use it as a pivot in your selection.
in other words, the algorithm is used recursively in two ways: first, on the sequence of medians, to find a good 
pivot, and second, on the original sequence, using this pivot.
While the algorithm is important to know about for theoretical reasons because it means selection can be done in 
guaranteed linear time, you’ll probably never actually use it in practice. 

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
125
Sorting by Halves
Finally, we’ve arrived at the topic most commonly associated with the divide-and-conquer strategy: sorting. I’m 
not going to delve into this too deeply, because Python already has one of the best sorting algorithms ever devised 
(see the “Black Box” sidebar about timsort, later in this section), and its implementation is highly efficient. In fact, 
list.sort is so efficient, you’d probably consider it as a first choice in place of other, asymptotically slightly better 
algorithms (for example, for selection). Still, the sorting algorithms in this section are among the most well-known 
algorithms, so you should understand how they work. Also, they are a great example of the way divide and conquer is 
used to design algorithms.
Let’s first consider one of the celebrities of algorithm design: C. A. R. Hoare’s quicksort. It’s closely related to the 
selection algorithm from the previous section, which is also due to Hoare (and sometimes called quickselect). The 
extension is simple: If quickselect represents traversal with pruning—finding a path in the recursion tree down to the 
kth smallest element—then quicksort represents a full traversal, which means finding a solution for every k. Which is 
the smallest element? The second smallest? And so forth. By putting them all in their place, the sequence is sorted. 
Listing 6-4 shows a version of quicksort.