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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фактический вопрос заключался в следующем: когда такой сценарий (почти отсортированный) может произойти с естественным входом?

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

Итак, чтобы ответить на актуальный вопрос

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

• Использование почти хронологических данных. У вас есть данные, которые обычно поступают в хронологическом порядке, но иногда некоторые элементы находятся не на своем месте. (Рассмотрите многопоточную среду, добавляющую в список элементы с отметками времени. Условия гонки могут привести к тому, что элементы будут добавляться в порядке, отличном от того, в котором они были проставлены отметками времени.) В этой ситуации, если вам нужны отсортированные данные, вы должны повторно -Сортировать. Потому что порядок данных не гарантируется.

• Добавление элементов в список: если у вас есть отсортированный список и вы просто добавляете некоторые элементы (т. е. без использования двоичной вставки). Вам нужно будет пересортировать почти отсортированный список.

• Данные из внешнего источника. Если вы получаете данные из внешнего источника, может не быть гарантии их сортировки. Так что сортируй сам. Однако, если внешний источник отсортирован, вам придется пересортировать данные.

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

• Перемежающиеся данные. Если вы получаете данные из нескольких отсортированных источников с перекрывающимися ключами, вы можете получить ключи, похожие на следующие: 1 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18. Несмотря на то, что половина элементов не соответствует порядку своих соседей, список почти отсортирован. Конечно, использование быстрой сортировки с опорой на первый элемент показало бы O(n^2) производительность.

Вывод

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

В качестве примечания: один из обычно худших алгоритмов сортировки, на самом деле неплохо справляется с почти отсортированными данными. В приведенных выше данных с чередованием для пузырьковой сортировки требуется всего 9 операций подкачки. Его производительность на самом деле будет O(n).

Из быстрой сортировки

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

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

худший случай в быстрой сортировке:

1. Все элементы массива одинаковы
2. Массив уже отсортирован в том же порядке
3. Массив уже отсортирован в обратном порядке.

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