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

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

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

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

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

5 Solutions collect form web for “Быстрая сортировка Наихудший случай”

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

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

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

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

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

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

Итак, за 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)

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

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

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

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

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

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

Путь к этой проблеме состоит в том, чтобы разделить на три раздела: нижний (элементы

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

  • TMP: как обобщить декартово произведение векторов?
  • Детали реализации оборудования с плавающей запятой
  • Найти XOR всех чисел в заданном диапазоне
  • Дифф-алгоритм?
  • Алгоритм определения периодов перекрытия
  • Алгоритм подсчета сумм
  • Вычисление pow (a, b) mod n
  • алгоритм проверки соединения четырех полей
  • Магический номер в boost :: hash_combine
  • Наибольший простой коэффициент числа
  • Сравнение строк порядка сортировки в Java - один встроенный?
  • Interesting Posts

    Как получить случайную строку текстового файла в Java?

    Присоединить два файла WAV от Java?

    Использование iptables для перенаправления IP-адреса

    Java swing JComponent “размер”

    Как вы завершаете или перезагружаете компьютер Windows через подключение к удаленному рабочему столу?

    Активность, AppCompatActivity, FragmentActivity и ActionBarActivity: когда использовать что?

    Дессериализация XML для объектов в C #

    Как я могу переделать и форматировать «USB-накопитель USB-накопителя Toshiba USB 2.0», содержащий раздел CDFS?

    Как я могу вернуть старый стиль меню в Chrome 28, теперь, когда был отключен переключатель –disable-new-menu-style?

    Почему Firefox не распознает быстрые клавиши приложения, созданные в Mac OS X System Preferences?

    Когда использовать struct?

    JSTL c: forEach на странице JSP не работает

    Создание пакетов в linq

    не может загрузить такой файл – sqlite3 / sqlite3_native (LoadError) на rubyе на рельсах

    Ошибка после обновления pip: невозможно импортировать имя ‘main’

    Давайте будем гением компьютера.