|
|
< Day Day Up > |
|
The quicksort procedure was invented by Hoare [147]; Hoare's version appears in Problem 7-1. The PARTITION procedure given in Section 7.1 is due to N. Lomuto. The analysis in Section 7.4 is due to Avrim Blum. Sedgewick [268] and Bentley [40] provide a good reference on the details of implementation and how they matter.
McIlroy [216] showed how to engineer a "killer adversary" that produces an array on which virtually any implementation of quicksort takes Θ(n2) time. If the implementation is randomized, the adversary produces the array after seeing the random choices of the quicksort algorithm.
|
|
< Day Day Up > |
|