Быстрая сортировка против сортировки слиянием
Почему быстрая сортировка может быть лучше, чем сортировка слиянием?
11 ответов
Смотрите Quicksort в Википедии:
Как правило, быстрая сортировка на практике значительно быстрее, чем другие алгоритмы Θ(nlogn), потому что ее внутренний цикл может быть эффективно реализован на большинстве архитектур, а в большинстве реальных данных можно сделать выбор проекта, который сводит к минимуму вероятность необходимости квадратичной время.
Обратите внимание, что очень низкое требование к памяти также является большим плюсом.
Быстрая сортировка обычно выполняется быстрее, чем сортировка слиянием, когда данные хранятся в памяти. Однако, когда набор данных огромен и хранится на внешних устройствах, таких как жесткий диск, сортировка слиянием является явным победителем в плане скорости. Он минимизирует дорогостоящее чтение с внешнего диска, а также хорошо подходит для параллельных вычислений.
Для сортировки Merge худший случай O(n*log(n)), для быстрой сортировки: O(n2), Для других случаев (в среднем, лучше) оба имеют O(n*log(n)), Однако быстрая сортировка - это постоянная пространства, где сортировка слиянием зависит от структуры, которую вы сортируете.
Смотрите это сравнение.
Вы также можете увидеть это визуально.
Хотя быстрая сортировка часто является лучшим выбором, чем сортировка слиянием, безусловно, бывают случаи, когда сортировка слиянием является лучшим выбором. Наиболее очевидное время - это когда крайне важно, чтобы ваш алгоритм работал быстрее, чем O(n^2). Быстрая сортировка обычно быстрее, чем эта, но, учитывая теоретически худшие входные данные, она может работать в O(n^2), что хуже, чем наихудшая сортировка слиянием.
Быстрая сортировка также более сложна, чем сортировка слиянием, особенно если вы хотите написать действительно надежную реализацию, и поэтому, если вы стремитесь к простоте и удобству обслуживания, сортировка слиянием становится многообещающей альтернативой с минимальными потерями производительности.
Я лично хотел проверить разницу между быстрой сортировкой и сортировкой слиянием самостоятельно и увидел время выполнения для выборки из 1 000 000 элементов.
Быстрая сортировка смогла сделать это за 156 миллисекунд, тогда как сортировка слиянием сделала то же самое за 247 миллисекунд
Данные быстрой сортировки, однако, были случайными, и быстрая сортировка работает хорошо, если данные случайные, в отличие от сортировки слиянием, т.е. сортировка слиянием выполняется независимо от того, сортируются или нет данные. Но сортировка слиянием требует одного полного дополнительного пространства, а быстрая сортировка - не как сортировка на месте.
Я написал комплексную рабочую программу, для них тоже будут иллюстративные картинки.
Быстрая сортировка на месте. Вам просто нужно поменять позиции данных во время функции разделения. Mergesort требует намного больше копирования данных. Вам нужно другое временное хранилище (обычно того же размера, что и исходный массив данных) для функции слияния.
В дополнение к другим: сортировка слиянием очень эффективна для неизменяемых структур данных, таких как связанные списки, и поэтому является хорошим выбором для (чисто) функциональных языков программирования.
Плохо реализованная быстрая сортировка может быть угрозой безопасности.
Быстрая сортировка названа так по причине,
Основные моменты: оба вида являются стабильными (просто неприятность реализации), поэтому давайте просто перейдем к сложностям
это очень сбивает с толку только из-за того, что нотации big-oh разлиты и "злоупотреблены", в обоих случаях средняя сложность случая равна 0(nlogn),
но сортировка слиянием всегда равна 0(nlogn), тогда как быстрая сортировка для плохих разделов, то есть перекошенных разделов, таких как 1 элемент-10 (что может произойти из-за отсортированного или обратного отсортированного списка), может привести к 0 (n^2)..
.. и поэтому мы имеем рандомизированную быструю сортировку, где мы выбираем основную точку случайным образом и избегаем такого перекошенного разбиения, тем самым сводя на нет весь сценарий n^2 в любом случае даже для умеренно перекошенного разбиения, такого как 3-4, у нас есть nlog(7/4)n в идеале мы хотим получить 1-1, таким образом, целые 2 из O(nlog(2)n).
так что это O(nlogn), почти всегда и в отличие от сортировки слиянием константы, спрятанные под нотацией "большой-ой", лучше для быстрой сортировки, чем для сортировки слиянием... и она не использует дополнительное пространство, как сортировка слиянием.
но для правильной работы быстрой сортировки требуется настроить, перефразировать, быстрая сортировка дает вам возможность настроить....
Ответ будет слегка наклонен в сторону быстрой сортировки по отношению к изменениям, внесенным с помощью DualPivotQuickSort для примитивных значений. Используется в JAVA 7 для сортировки в java.util.Arrays
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
Это не правда, что быстрая сортировка лучше. Кроме того, это зависит от того, что вы имеете в виду лучше, потребление памяти или скорость.
С точки зрения потребления памяти, в худшем случае, но быстрая сортировка может использовать n^2 памяти (т.е. каждый раздел от 1 до n-1), тогда как сортировка слиянием использует nlogn.
Вышеизложенное следует с точки зрения скорости.
Быстрая сортировка на месте. Вам нужно очень мало дополнительной памяти. Что крайне важно.
Хороший выбор медианы делает его еще более эффективным, но даже плохой выбор медианных гарантий Тета (nlogn).