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

Question

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

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

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

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

Answer 1

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

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

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

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

Answer 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) Выберите медиану первых пяти элементов в каждом наборе так: (3) (23) (43) (63) (83)

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

Answer 3

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

Answer 4

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

Answer 5

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

• выбор оси
• как разделить вокруг оси

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

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

Способ обойти эту проблему - разделить на три раздела: нижний (элементы

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

Answer 6

Мне часто задают вопрос.AFAI исследования есть 2 ключа его худшего.

• Если массив уже отсортирован, независимо от того, восходящий или нисходящий в дополнение к , выбирая поворот как минимальный (самый маленький) или максимальный(наибольшее) элемент списка.[2,3,4] или [4,3,2]
• Если все элементы одинаковы.[2,2,2]