Можно ли добиться постоянного O(nlogn) для квиксорта в любом случае?

Question

[Егор Полянский]

Можно ли добиться постоянного O(nlogn) для квиксорта в любом случае?

Answer 1

[Everything_is_bad]

Элементарно же, давай включим логику, про O(n log n) известно что это в среднем, значит есть случаи, когда это не работает, отсюда вывод, постоянного O(n log n) для квиксорта в любом случае не добиться.

Comments

[Василий Банников]

известно что это в среднем

У big o другое определение.

Если максимально простым язом, то big o - это верхняя граница роста исследуемой функции за исключением граничных случаев.

Для обозначения асимптоты для худшего случая используется омега (хуже чем омега, исследуемая функция не растёт).

Вот у классического квиксорта есть граничный случай, который проявляется на отсортированных или почти отсортированными последовательностях - у него возникает N^2, где N - количество элементов.

Автор вопроса по сути спрашивает, можно ли как-то модифицировать квиксорт так, чтобы этих граничных случаев не было.

big o в таком случае будет равняется омеге и оба будут nlogn

Answer 2

[Василий Банников]

Dual-Pivot Quicksort должен решать проблему с почти отсортированными массивами, но у него тоже существует worst case сценарий с n^2 (массив уже отсортирован полностью по убыванию либо возрастанию), но этого хотя бы можно избежать, добавив проверку, что массив уже отсортирован (делается в один проход)

Answer 3

[Wataru]

Да, можно. Для этого надо в качестве pivot'а выбрать медиану. если это сделать за O(n) в худшем случае, то общая сложность QuickSort'а будет O(n log n).

Для выбора медианы за O(n) есть, например, вот такой алгоритм. В каких-то источниках его еще называли алгоритмом кнута-пратта-мориса-ривеста-тарьяна. Кажется, но я их найти не могу, так что я какие-то фамилии напутал, но помню, что там было 5 великих информатиков.

На практике же это не применяют, потому что этот алгоритм хоть и имеет линейную сложность в худшем, константа там такая, что там на квадрат хватит и еще на логарифм сверху останется. Просто используя какие-нибудь случайные числа можно добиться гораздо лочшей производительности.

Answer 4

[Mercury13]

Наиболее распространённый метод — IntroSort. Если рекурсия ушла глубоко, переключиться на другой метод. Постоянные n log n и не теряются классные свойства QuickSort.

Да, есть методы именно на быстрой сортировке, но, видимо, умные люди всё испытали и ничего лучшего не нашли.