Худший случай для QuickSort - когда это может произойти?

Из Quicksort

для быстрой сортировки, «худший случай» соответствует уже отсортированному

Список со всеми элементами с одинаковым номером уже отсортирован .

Я думаю, что люди путают Quicksort с алгоритмом сортировки на основе разделов и "qsort" различные реализации библиотеки.

Я предпочитаю видеть алгоритм быстрой сортировки как имеющий подключаемый алгоритм выбора точки поворота, что очень важно при анализе его поведения.

Если в качестве опорного всегда выбирается первый элемент, то уже отсортированный список является наихудшим случаем.Часто существует высокая вероятность того, что массив уже / почти отсортирован, поэтому эта реализация довольно плохая.

Аналогично, выбор последнего элемента в качестве точки поворота плох по той же причине.

Некоторые реализации пытаются избежать этой проблемы, выбирая средний элемент в качестве опорного. Это не будет работать так плохо с уже / почти отсортированными массивами, но все же можно создать ввод, который использовал бы этот предсказуемый выбор точки поворота и заставил бы его работать за квадратичное время.

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

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

Итак, некоторые углы срезаны, и люди разработали алгоритм медианы трех. Конечно, позже даже это было использовано так называемым «убийцей» среднего из трех.

Таким образом, делается больше попыток придумать более «интеллектуальные» алгоритмы выбора точки поворота, которые гарантируют O (N log N) асимптотическое поведение, которое все еще достаточно быстрое, чтобы быть практичным, с различной степенью успеха.

Итак, на самом деле, если не указать конкретную реализацию Quicksort, вопрос о том, когда наступает худший сценарий, не определен. Если вы используете так называемый алгоритм выбора опорной точки медианы медианы, худшего сценария квадратичного решения не существует.

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

Я считаю, что худший случай для быстрой сортировки зависит от выбора элемента поворота на каждом этапе. Быстрая сортировка имеет худшую производительность, если точка поворота может быть либо наименьшим, либо наибольшим элементом в списке (например, первым или последним элементом уже отсортированного списка).

Если, например, вы выбираете средний элемент списка, уже отсортированный список не имеет наихудшего времени выполнения.

Итак, если вы подозреваете, что ваш сценарий, скорее всего, является плохим сценарием для быстрой сортировки, вы можете просто изменить свой выбор опорного элемента, чтобы быстрая сортировка работала лучше.

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