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

Question

При анализе QS каждый всегда ссылается на «почти отсортированный» наихудший случай. Когда такой сценарий может произойти с естественным вкладом?

Единственный пример, который я привел, - это повторная индексация.

Answer 1

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

Фактический вопрос был: «Когда такой сценарий (почти отсортированный) может произойти с естественным вкладом?».

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

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

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

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

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

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

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

• Чередованные данные : Если вы получаете данные из нескольких отсортированных источников с перекрывающимися ключами, вы можете получить ключи, похожие на следующие: 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).

Answer 4

С Быстрая сортировка

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

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

Answer 5

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

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

Answer 6

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