开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜