Cormen quicksort
In the book Introduction to Algorithms, the quicksort algorithm described in the chapter Quicksort does not employ Hoare-Partitioning.
Can anyone enlighten me with the advantage of this approach over the popular hoar开发者_Go百科e-partitioning. Or is it that its just a matter of choice for the author ?
A note in the second edition (the changelog since the first) says (emphasis mine):
The partitioning method used for quicksort (Section 7.1) and the expected linear-time order-statistic algorithm (Section 9.2) is different. We now use the method developed by Lomuto, which, along with indicator random variables, allows for a somewhat simpler analysis. The method from the first edition, due to Hoare, appears as a problem in Chapter 7.
精彩评论