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

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

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

12.12.2008 05:50:35
Мне трудно купить заявление, что быстрая сортировка медленнее, чем сортировка вставкой. Покажите свой код.
Juliet 12.12.2008 06:01:23
Почему для небольших наборов данных быстрая сортировка медленнее, чем сортировка вставкой.
user549612 21.12.2010 07:44:39
11 ОТВЕТОВ

Возможно, вас заинтересуют эти алгоритмы сортировки .

6
12.12.2008 06:00:36

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

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

2
12.12.2008 06:02:15

Самые быстрые реализации быстрой сортировки используют зацикливание вместо рекурсии. Рекурсия обычно не очень быстрая.

0
12.12.2008 06:08:39

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

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

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

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

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

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

1
12.12.2008 06:09:25

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

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

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

2
12.12.2008 06:09:41

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

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

0
12.12.2008 06:46:31

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

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

0
12.12.2008 06:58:55

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

0
12.12.2008 08:00:02

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

0
11.11.2009 14:46:32

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

1
27.08.2012 13:04:21

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

0
15.11.2013 04:54:34