Быстрая сортировка Наихудший случай

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

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

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

Хороший алгоритм будет хорошим.

Спасибо

Ответ 1

Производительность Quicksort зависит от вашего алгоритма выбора сводных данных. Самый наивный алгоритм выбора опорных точек - это просто выбрать первый элемент в качестве свода. Легко видеть, что это приводит к худшему поведению, если ваши данные уже отсортированы (первым элементом всегда будет min).

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

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

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

Ответ 2

Худшее состояние производительности:

Когда каждый раз выбранный выбор является "наибольшим" или "самым маленьким", и этот образец повторяется

Итак, для 1 3 5 4 2

Если повороты выбраны в порядке 1,2,3,4,5 или 5,4,3,2,1

тогда наихудшее время работы O (n * n)

Как избежать наихудшего случая:

(1) Разделите массив на пять множеств. Итак, если 1..100 множества (1..20) (21..40) (41..60) (61..80) (81.. 100)

(2) Выберите медиану первых пяти элементов в каждом из множества so (3) (23) (43) (63) (83)

(3) Теперь выберите медианную среди них как ось вращения, так что здесь (43)

Ответ 3

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

Ответ 4

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

Ответ 5

В худшем случае время работы зависит от метода разбиения в quick-sort. Это имеет два аспекта:

выбирая стержень
как разбить вокруг оси

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

это приводит к тому, что partion вызывается n раз, каждый из которых принимает n/2 в среднем, ведущий к O (n²)
Это нехорошо, потому что это не теоретический худший сценарий, а довольно общий.
обратите внимание, что он не решается путем обнаружения пустого раздела, поскольку стержень может иметь наивысшее или низкое значение элемента (например, медианное значение равно 5, которое также является наивысшим значением элемента, но все равно может быть несколько неулокальных < 5 значений)

Способом решения этой проблемы является разделение на три раздела, более низкое (элементы < pivot), равное (элементы = поворот) и верхний раздел. "= Стержневые элементы" находятся в конечном положении. Более низкий и верхний раздел нуждается в сортировке, если не пустой.

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