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

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

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

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

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

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

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

Заключение

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

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

Ответ 4

От Quicksort

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

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

Ответ 5

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

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

Ответ 6

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