Быстрая сортировка против сортировки слиянием [дубликат]

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

для сортировки слиянием худшим случаем является O(n*log(n)), для быстрой сортировки: O(n²). Для других случаев (avg, best) оба имеют O(n*log(n)). Однако быстрая сортировка-это постоянная пространства, где сортировка слиянием зависит от структуры, которую вы сортируете.

посмотреть это сравнение.

вы также можете увидеть это визуально.

Я лично хотел проверить разницу между быстрой сортировкой и сортировкой слиянием и увидел время выполнения для выборки из 1 000 000 элементов.

быстрая сортировка смогла сделать это за 156 миллисекунд а сортировка слиянием сделала то же самое за 247 миллисекунд

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

Я написал комплексную рабочую программу для них будут иллюстративные фотографии тоже.

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

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

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

плохо реализованный quicksort может быть угрозу безопасности.

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

quicksort назван так не просто так,

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

его очень запутывают только большие обозначения, которые проливаются и "злоупотребляются", оба имеют среднюю сложность случая 0(nlogn),

но сортировка слиянием всегда равна 0 (nlogn), тогда как quicksort для плохих разделов, т. е. перекошенных разделов, таких как 1 элемент-10 элемент (что может произойти из-за сортировки или обратный отсортированный список) может привести к 0(n^2)..

.. и поэтому мы рандомизировали quicksort, где мы выбираем ось случайным образом и избегаем такого искаженного разбиения, тем самым сводя к нулю весь сценарий n^2 во всяком случае , даже для умеренно перекошенного разбиения, такого как 3-4, у нас есть nlog (7/4)n, в идеале мы хотим 1-1 часть, таким образом, все 2 из O(nlog(2)n).

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

но получение quicksort run отлично требует настройки, перефразирования, quicksort предоставляет вам возможности для настройки ....

ответ будет слегка наклоняться в сторону quicksort w.r .t к изменениям, внесенным с помощью DualPivotQuickSort для примитивных значений. Он используется в JAVA 7 сортировать java.утиль.Массивы

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

вы можете найти имплментацию JAVA7 здесь - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Читать далее удивительные по DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Это не правда, что quicksort лучше. Кроме того, это зависит от того, что вы имеете в виду лучше, потребление памяти, или скорость.

с точки зрения потребления памяти, в худшем случае, но quicksort может использовать память n^2 (т. е. каждый раздел От 1 до n-1), тогда как сортировка слиянием использует nlogn.

выше образом с точки зрения скорости.

Quicksort на месте. Вам нужно очень мало дополнительной памяти. Что крайне важно.

хороший выбор медианы делает его еще более эффективным, но даже плохой выбор медианных карантинов тета(nlogn).