Средняя сложность времени быстрой сортировки и сортировки вставкой

Question

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

У меня есть теория: quiksort работает медленнее, потому что он рекурсивный, и вызов, который он выполняет для собственной сигнатуры метода, довольно медленный в JVM, поэтому мой таймер дает намного более высокие показания, чем я ожидал, тогда как вставка не рекурсивная и вся эта работа выполняется в рамках одного метода, поэтому JVM не нужно выполнять дополнительную работу? amirite

Answer 1

Вас могут заинтересовать эти Анимации алгоритма сортировки .

Answer 2

Если вы не достигли одного из патологических случаев Quicksort (часто это список, который уже отсортирован), Quicksort должен быть O (n log n) - существенно быстрее, чем O (n ^ 2) сортировки вставки при увеличении n.

Возможно, вы захотите использовать сортировку слиянием или сортировку кучи; у них нет патологических случаев. Они оба O (n log n).

(Когда я делал это давным-давно на C ++, быстрая сортировка была быстрее, чем сортировка вставкой с довольно маленькими n с. Radix заметно быстрее со средними n с. )

Answer 3

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

У JVM не должно быть проблем с рекурсивными вызовами.

Answer 4

На самом деле для малого значения n сортировка вставкой лучше, чем быстрая сортировка. Что касается малого значения n вместо n ^ 2 или nlogn, время зависит больше от константы.

Answer 5

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

Полагаю, различия должны заключаться в способе реализации QS:

выбор разворота для заданных данных? (3-медиана - лучший подход)

используя тот же механизм Swap для QS и сортировки вставок?

- это случайный входной enuf, т. Е. Если у вас есть кластеры упорядоченных данных, производительность будет
страдать.

Я выполнил это упражнение на языке Си, и результаты соответствуют теории.

Answer 6

На самом деле для малой стоимости n тип вставки полезнее, чем быстрый тип. Что касается малой ценности n, а не n ^ 2 или nlogn, время сильно зависит от константы. Веб-разработка Индианаполис

Answer 7

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

Answer 8

Здесь нужно учесть три вещи. Во-первых, сортировка вставкой выполняется намного быстрее ( O (n) против O (n log n) ), чем быстрая сортировка, если набор данных уже отсортирован или почти завершен; во-вторых, если набор данных очень мал, «время запуска» для настройки быстрой сортировки, поиска точки поворота и т. д. доминирует над остальными, а в-третьих, быстрая сортировка немного неуловима, вы можете перечитать код после ночного сна.

Answer 9

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

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

Answer 10

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

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