Здравствуйте, _DAle_, Вы писали:

EP>>Это их фейл.
EP>>Даже Степанов этот момент упоминал, конкретно Lomuto vs Hoare partition в CLRS (34:18):
EP>>https://youtu.be/d4tFGtGngf4?t=2058
EP>>ЕМНИП даже кто-то из CLRS это в своей лекции что-то такое упоминал.
_DA>Окей. Я не согласен. Я считаю, что тот конкретный алгоритм, который когда-то описал Хоар — это одна из реализаций того, что сейчас называется Quicksort (а та конкретная называется сортировкой Хоара). На мой взгляд, сейчас (а не в прошлом веке) по термином Quicksort подразумевают семейство алгоритмов (например, в той же википедии это так), с конкретным подходом: divide and conquer + pivot, и вполне определенной временной сложностью по времени в среднем и худшем случае.

Ошибаются, IMO. Также как и часто путают selection sort и bubble sort. Также как и отнесли трюк с логарифмическим стеком Седжвику.

_DA>Если считать, что, например, Lomuto partition — это уже не Quicksort, не in-place реализация — не Quicksort, тогда отсутствие хвостовой рекурсии — это тоже не Quicksort?

В статье, ссылку на которую я привёл, вообще описывается явный стек (nest). Существенным моментом здесь является не tail-call сам по себе, а гарантия лографмического размера — вполне алгоритмическая черта.

_DA>А переход на insertion sort для малых интервалов — это Quicksort или нет?

Это будет гибрид. Например часто в реализациях std::sort используется следующая схема: начинаем с quicksort, в середине можем перейти на heapsort (чтобы получить линеаритмический худший случай) и заканчиваем insertion sort — и для этого варианта есть специальное отдельное название — introsort.

_DA>Если Quicksort — это только то, что Хоар описал в 60-х, так она тогда на практике и не используется нигде (в модуле turbo pascal разве что..

Quicksort используется в гибридах типа introsort, которая используется в реализациях STL, потому что она действительно quick, как раз из-за inplace'ности и unguarded bidirectional partition — то чего нет в коде из первого сообщения.

_DA>а хотя стойте, там же нет хвостовой рекурсии ).

Причём тут "нет хвостовой рекурсии"? Она элементарно "эмулируется" вручную.

_DA>В целом, я за позицию wikipedia и Кормена et al.

Применение Lomuto partition для подобной сортировки — это крайне нерационально. Степанов объяснил почему — получается крайне неэффективно, так как намного чаще вырождается в квадратичность.
Для алгоритмического курса это действительно фейл.


В общем, я за то чтобы называть quicksort'ом только вариации близкие к оригинальной статье Хоара по двум причинам:
1) Сортировка называется quicksort — этот quick является неотъемлемой её частью.
2) Замечательный факт в том, что алгоритм шестидесятых годов, разрабатываемый под те железные реалии, остаётся крайне актуальным (действительно quick) и в наше время. И это как раз благодаря тем чертам, которых нет в коде из первого сообщения, и которые подробно описаны в оригинальной статье. Если же мы будем называть любую концептуально медленную вариацию этим именем — то связь с оригиналом действительно будет размываться.