Почему быстрая сортировка лучше, чем слияние?

Question

Мне задали этот вопрос во время интервью. Они оба O (nlogn), и все же большинство людей используют Quicksort вместо Mergesort. Почему это так?

Answer 1

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

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

По этим причинам я больше поклонник Mergesort, чем Quicksort.

Answer 2

Небольшие дополнения к быстрой сортировке и сортировке.

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

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

Кроме того, в пользовательских контейнерах, таких как «связанный список», быстрая сортировка не дает никаких преимуществ.
1. Объединить сортировку в связанный список, не нужно дополнительной памяти. 2. Доступ к элементам в быстрой сортировке не последовательный (в памяти)

Answer 3

Трудно сказать. Худший из MergeSort - это n (log2n) -n + 1, что точно, если n равно 2 ^ k (я это уже доказал). И для любого n это между (n lg n - n + 1) и (n lg n + n + O (lg n)). Но для быстрой сортировки лучше всего использовать nlog2n (также n равно 2 ^ k). Если разделить Mergesort на quickSort, она равна единице, когда n бесконечно. Так что как будто худший случай MergeSort лучше, чем лучший вариант QuickSort, почему мы используем быструю сортировку? Но помните, MergeSort не на месте, он требует 2n memeroy пробела. И MergeSort также нужно сделать много копий массива , который мы не включаем в анализ алгоритма. Одним словом, MergeSort действительно быстрее, чем быстрая сортировка в theroy, но в действительности вам нужно учитывать пространство памяти, стоимость копирования массива, слияние медленнее, чем быстрая сортировка. однажды провел эксперимент, в котором мне дали 1000000 цифр в java по классу Random, и это заняло 2610 мс при сортировке слиянием, 1370 мс при быстрой сортировке.

Answer 4

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

Мне интересно, почему так редко можно увидеть radix или сортировку ведер. Они O (n), по крайней мере, в связанных списках, и все, что нужно, это какой-то метод преобразования ключа в порядковое число. (Строки и числа с плавающей точкой работают отлично.)

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

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

Edit: На самом деле, вот еще более порочный способ сортировки чисел с плавающей точкой: http://www.stereopsis.com/radix.html. Обратите внимание, что трюк с переключением битов можно использовать независимо от того, какой алгоритм сортировки вы на самом деле используете ...

Answer 5

Учитывайте сложность времени и пространства. Для сортировки слиянием: Временная сложность: O (nlogn), Пространство сложности: O (nlogn)

Для быстрой сортировки: Временная сложность: O (n ^ 2), Пространственная сложность: O (n)

Теперь они оба выигрывают по одному сценарию каждый. Но, используя случайный круг, вы почти всегда можете уменьшить сложность времени быстрой сортировки до O (nlogn).

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

Answer 6

Одна из причин более философская. Быстрая сортировка - это философия Top-> Down. С n элементов для сортировки, есть n! возможности. С двумя разделами m & n-m, которые являются взаимоисключающими, количество возможностей уменьшается на несколько порядков. м! * (н-м)! меньше на несколько порядков чем n! в одиночестве. представь 5! против 3! * 2 !. 5! имеет в 10 раз больше возможностей, чем 2 раздела по 2 и 3 каждый. и экстраполировать до 1 миллиона факториалов против 900K! * 100K! Так что вместо того, чтобы беспокоиться об установлении какого-либо порядка в пределах диапазона или раздела, просто установите порядок на более широком уровне в разделах и уменьшите возможности внутри раздела. Любой порядок, установленный ранее в пределах диапазона, будет нарушен позже, если сами разделы не являются взаимоисключающими.

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

Быстрая сортировка подобна управленческому подходу, когда изначально никто не заботится о каком-либо заказе, а только о соответствии широкому критерию без учета заказа. Затем разделы сужаются, пока вы не получите отсортированный набор. Настоящая проблема в быстрой сортировке - найти раздел или критерий в темноте, когда вы ничего не знаете об элементах для сортировки. Вот почему мы должны либо потратить некоторое усилие, чтобы найти медианное значение, либо выбрать 1 наугад, либо какой-нибудь произвольный «управленческий» подход. Чтобы найти идеальную медиану, может потребоваться значительное количество усилий и снова привести к глупому подходу снизу вверх. Итак, Quicksort говорит, что нужно просто выбрать случайный опорный пункт и надеяться, что он будет где-то посередине или поработает, чтобы найти медиану 3, 5 или что-то еще, чтобы найти лучшую медиану, но не планируйте быть идеальным и не тратьте любое время в первоначальном порядке. Похоже, что это хорошо, если вам повезло или иногда ухудшается до n ^ 2, когда вы не получаете медиану, а просто рискуете. В любом случае данные случайны. право. Поэтому я больше согласен с логическим подходом сверху -> вниз к быстрой сортировке, и оказывается, что вероятность, которую он использует для выбора и сравнения сводок, которые он сохраняет ранее, работает лучше больше раз, чем любой тщательный и тщательный стабильный подход снизу вверх, например Сортировка слиянием. Но

Answer 7

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

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

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

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

РЕДАКТИРОВАТЬ: я только что обнаружил, что сортировка слиянием худший / лучший / средний регистр всегда nlogn, но быстрая сортировка может варьироваться от n2 (наихудший случай, когда элементы уже отсортированы) до nlogn (avg / лучший случай, когда сводка всегда делит массив в две половинки).

Answer 8

В c / c ++ land, когда я не использую контейнеры stl, я склонен использовать быструю сортировку, потому что она построена во время выполнения, в то время как сортировка слиянием не.

Так что я считаю, что во многих случаях это просто путь наименьшего сопротивления.

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