Cormen Quicksort

Question

В книге «Введение в алгоритмы» алгоритм быстрой сортировки, описанный в главе «Быстрая сортировка», не использует Hoare-Partitioning.

Может кто-нибудь просветить меня преимуществом этого подхода по сравнению с популярным разделением Hoare.Или это просто вопрос выбора автора?

Answer 1

В примечании во втором издании (журнал изменений после первого) говорится ( выделение мое):

Метод разделения, используемый для быстрой сортировки (раздел 7.1) и ожидаемый Алгоритм статистики линейного времени (раздел 9.2) отличается. Теперь мы используем метод, разработанный Ломуто, который, наряду с индикатором случайных величин, допускает несколько более простой анализ . Метод из первого издания, из-за Хоару, кажется проблемой в главе 7.