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

Question

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

Answer 1

Я хотел бы добавить к существующим отличным ответам некоторую математику о том, как QuickSort работает при отклонении от лучшего случая и насколько это вероятно, что, я надеюсь, поможет людям немного лучше понять, почему случай O (n ^ 2) не имеет большого значения для более сложных реализаций QuickSort.

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

1) Небольшое количество ключей в данных. Набор данных с одним и тем же значением будет отсортирован за n ^ 2 раз на ванильной 2-секционной быстрой сортировке, потому что все значения, кроме местоположения центра, каждый раз размещаются на одной стороне. Современные реализации решают эту проблему такими методами, как использование 3-секционной сортировки. Эти методы выполняются для набора данных с одинаковым значением за O (n) раз. Таким образом, использование такой реализации означает, что ввод с небольшим количеством клавиш фактически увеличивает время выполнения и больше не является проблемой.

2) Чрезвычайно неудачный выбор поворота может привести к худшему результату. В идеальном случае опорная точка всегда будет такой, что 50% данных будут меньше, а 50% - больше, так что вход будет разбит пополам во время каждой итерации. Это дает нам n сравнений и свопов log-2 (n) рекурсий за O (n * logn).

Насколько неидеальный круговой выбор влияет на время выполнения?

Давайте рассмотрим случай, когда стержень последовательно выбирается таким образом, чтобы 75% данных находились на одной стороне стержня. Это все еще O (n * logn), но теперь база журнала изменилась на 1 / 0,75 или 1,33. Отношение в производительности при изменении базы всегда является константой, представленной log (2) / log (newBase). В этом случае эта константа равна 2,4. Так что это качество выбора разворота занимает в 2,4 раза больше времени, чем идеальное.

Как быстро все ухудшается?

Не очень быстро, пока выбор точки разворота не станет (последовательно) очень плохим:

• 50% с одной стороны: (идеальный случай)
• 75% с одной стороны: в 2,4 раза длиннее
• 90% с одной стороны: в 6,6 раза длиннее
• 95% на одной стороне: в 13,5 раза длиннее
• 99% с одной стороны: в 69 раз больше

Когда мы приближаемся к 100% с одной стороны, лог-часть выполнения приближается к n, и все выполнение асимптотически приближается к O (n ^ 2).

В простой реализации QuickSort такие случаи, как отсортированный массив (для сводки 1-го элемента) или массив с обратной сортировкой (для сводки последнего элемента), будут надежно создавать время выполнения O (n ^ 2) в худшем случае. Кроме того, реализации с предсказуемым выбором поворота могут подвергаться DoS-атаке с помощью данных, предназначенных для выполнения в худшем случае. Современные реализации избегают этого с помощью различных методов, таких как рандомизация данных перед сортировкой, выбор медианы из 3 случайно выбранных индексов и т. Д. С этой рандомизацией в миксе мы имеем 2 случая:

• Небольшой набор данных. Наихудший случай вполне возможен, но O (n ^ 2) не является катастрофическим, поскольку n достаточно мало, чтобы n ^ 2 также было мало.
• Большой набор данных. Худший случай возможен в теории, но не на практике.

Насколько вероятно, что мы увидим ужасную производительность?

Шансы исчезающе малы . Давайте рассмотрим своего рода 5000 значений:

Наша гипотетическая реализация выберет опорную точку, используя медиану из 3 случайно выбранных индексов. Мы будем рассматривать «точки», которые находятся в диапазоне 25% -75%, как «хорошие», а точки, которые находятся в диапазоне 0% -25% или 75% -100%, являются «плохими». Если вы посмотрите на распределение вероятностей, используя медиану из 3 случайных индексов, у каждой рекурсии есть шанс 11/16 закончиться хорошим разворотом. Давайте сделаем 2 консервативных (и ложных) предположения для упрощения математики:

1. Хорошие точки разворота всегда точно на 25% / 75% и работают в 2,4 * идеальном случае. Мы никогда не получим идеальное разделение или любое разделение лучше, чем 25/75.

2. Плохие опорные точки всегда являются наихудшими случаями и, по сути, ничего не дают для решения.

Наша реализация QuickSort остановится на n = 10 и переключится на сортировку вставкой, поэтому нам потребуется 22 25% / 75% сводных раздела, чтобы разбить входное значение 5000 на столько. (10 * 1.333333 ^ 22> 5000) Или нам нужно 4990 наихудших опорных точек. Имейте в виду, что если мы накопим 22 хороших пивота в любой точке , тогда сортировка будет завершена, так что в худшем случае или что-то близкое к этому потребуется крайне неудача. Если бы нам потребовалось 88 рекурсий для фактического достижения 22 хороших опорных точек, необходимых для сортировки до n = 10, это было бы в 4 * 2,4 * идеальном случае или примерно в 10 раз больше времени выполнения идеального случая. Насколько вероятно, что мы не достигнем требуемых 22 хороших точек после 88 рекурсий?

Биномиальное распределение вероятностей может ответить на это, и ответ составляет около 10 ^ -18. (n равно 88, k равно 21, p равно 0,6875) Вероятность удара молнии за 1 секунду, которую требуется от молнии [SORT], у пользователя примерно в тысячу раз выше, чем при просмотре 5000 пунктов сортировки хуже чем 10 * идеальный случай. Этот шанс уменьшается по мере увеличения набора данных. Вот некоторые размеры массивов и соответствующие им шансы на запуск более 10 * идеально:

• Массив из 640 предметов: 10 ^ -13 (требуется 15 хороших точек разворота из 60 попыток)
• Массив из 5000 элементов: 10 ^ -18 (требуется 22 хороших пивота из 88 попыток)
• Массив из 40000 элементов: 10 ^ -23 (требуется 29 хороших опорных точек из 116)

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

Наконец, как уже упоминали другие, даже эти невероятно маловероятные случаи можно устранить, переключившись на сортировку кучи, если стек рекурсии заходит слишком глубоко. Таким образом, TLDR заключается в том, что для хороших реализаций QuickSort наихудший случай на самом деле не существует , потому что он был разработан и выполнение завершается за O (n * logn) времени.

Answer 2

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

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

Answer 3

Ответ будет слегка наклонен в сторону быстрой сортировки по отношению к изменениям, внесенным с помощью 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

Answer 4

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

Answer 5

В сортировке слиянием общий алгоритм:

1. Сортировка левого подмассива
2. Сортировка правильного подмассива
3. Объединить 2 отсортированных подмассива

На верхнем уровне объединение 2 отсортированных подмассивов включает в себя работу с N элементами.

На один уровень ниже, каждая итерация шага 3 включает в себя работу с N / 2 элементами, но вы должны повторить этот процесс дважды. Таким образом, вы по-прежнему имеете дело с 2 * N / 2 == N элементами.

На один уровень ниже, вы объединяете 4 * N / 4 == N элементов и так далее. Каждая глубина в рекурсивном стеке включает в себя объединение одинакового количества элементов во всех вызовах для этой глубины.

Вместо этого рассмотрим алгоритм быстрой сортировки:

1. Укажите опорную точку
2. Поместите опорную точку в правильном месте в массиве, со всеми меньшими элементами слева, и более крупными элементами справа
3. Сортировка левого подмассива
4. Сортировать правый подмассив

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

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

На один уровень ниже, вы имеете дело с 4 поднаборами с комбинированным размером N-3 по тем же причинам, что и выше.

Затем N-7 ... Затем N-15 ... Затем N-32 ...

Глубина вашего рекурсивного стека остается примерно одинаковой (logN). С сортировкой слиянием вы всегда имеете дело с N-элементным слиянием на каждом уровне рекурсивного стека. Однако при быстрой сортировке количество элементов, с которыми вы имеете дело, уменьшается при переходе в стек. Например, если вы посмотрите на глубину посередине рекурсивного стека, число элементов, с которыми вы имеете дело, равно N - 2 ^ ((logN) / 2)) == N - sqrt (N).

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

Answer 6

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

Answer 7

Это довольно старый вопрос, но так как я недавно имел дело с обоими, вот мой 2c:

Для сортировки слиянием необходимо в среднем ~ N log N сравнений. Для уже (почти) отсортированных массивов это уменьшается до 1/2 N log N, поскольку при слиянии мы (почти) всегда выбираем «левую» часть 1/2 N раз, а затем просто копируем правые 1/2 N элементы. Кроме того, я могу предположить, что уже отсортированный ввод заставляет предсказатель ветвления процессора сиять, но угадывает почти все ответвления правильно, тем самым предотвращая задержки конвейера.

Для быстрой сортировки в среднем требуется ~ 1,38 N log N сравнений. Он не очень выигрывает от уже отсортированного массива с точки зрения сравнений (однако он дает преимущества с точки зрения перестановок и, вероятно, с точки зрения предсказаний переходов внутри ЦП).

Мои тесты на довольно современном процессоре показывают следующее:

Когда функция сравнения является функцией обратного вызова (как в реализации qsort () libc), быстрая сортировка медленнее сортировки слиянием на 15% при случайном вводе и 30% для уже отсортированного массива для 64-битных целых чисел.

С другой стороны, если сравнение не является обратным вызовом, мой опыт показывает, что быстрая сортировка превосходит сортировку слиянием до 25%.

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

Так что, возможно, суть в следующем: если сравнение стоит дорого (например, функция обратного вызова, сравнение строк, сравнение многих частей структуры, в большинстве случаев переходящих на второй-четвертый «если», чтобы иметь значение) - есть вероятность, что вы будет лучше с сортировкой слиянием. Для более простых задач быстрая сортировка будет быстрее.

Тем не менее все сказанное ранее верно: - Быстрая сортировка может быть N ^ 2, но Седжвик утверждает, что хорошая рандомизированная реализация имеет больше шансов, что компьютер, выполняющий сортировку, будет поражен молнией, чем N ^ 2. - Mergesort требует дополнительного места

Answer 8

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

• QuickSort принимает N ^ 2 в худшем случае и NlogN в среднем. Худший случай происходит, когда данные отсортированы. Это может быть смягчено случайным перемешиванием перед началом сортировки.
• QuickSort не требует дополнительной памяти, занимаемой сортировкой слиянием.
• Если набор данных большой и в нем присутствуют идентичные элементы, сложность быстрой сортировки уменьшается, если используется трехстороннее разбиение. Больше нет идентичных предметов, лучше сортировка. Если все элементы идентичны, они сортируются по линейному времени. [Это реализация по умолчанию в большинстве библиотек]

Всегда ли Quicksort лучше, чем Mergesort?

Не совсем.

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

Примечание: В java функция Arrays.sort () использует Quicksort для примитивных типов данных и Mergesort для типов данных объектов. Поскольку объекты потребляют служебную память, поэтому добавленные небольшие накладные расходы для Mergesort могут не представлять проблемы с точки зрения производительности.

Ссылка : Посмотрите видеоролики QuickSort Неделя 3, курс алгоритмов Принстона на Coursera

Answer 9

Быстрая сортировка - наихудший случай O (n ^ 2), однако в среднем случае последовательно выполняется сортировка слиянием. Каждый алгоритм - O (nlogn), но вы должны помнить, что, говоря о Big O, мы не учитываем более низкие факторы сложности. Быстрая сортировка значительно улучшена по сравнению с сортировкой слиянием, когда речь идет о постоянных факторах.

Сортировка слиянием также требует O (2n) памяти, в то время как быстрая сортировка может быть выполнена на месте (требуется только O (n)). Это еще одна причина, по которой быстрая сортировка обычно предпочтительнее сортировки слиянием.

Дополнительная информация:

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

[5, 4, 3, 2, 1]

Если в качестве наименьшего или наибольшего числа в группе выбрано значение pivot, то быстрая сортировка будет выполняться за O (n ^ 2). Вероятность выбора элемента, который находится в наибольшем или наименьшем 25% списка, составляет 0,5. Это дает алгоритму шанс 0.5 быть хорошим стержнем. Если мы используем типичный алгоритм поворота выбора (скажем, выбирая случайный элемент), мы имеем 0,5 шанса выбрать хороший стержень для каждого выбора оси. Для коллекций большого размера вероятность всегда выбирать плохой шарнир составляет 0,5 * n. На основании этой вероятности быстрая сортировка эффективна для среднего (и типичного) случая.

Answer 10

Хотя они оба в одном классе сложности, это не значит, что они оба имеют одинаковое время выполнения. Быстрая сортировка обычно быстрее, чем сортировка слиянием, просто потому, что проще кодировать жесткую реализацию, а выполняемые ею операции могут выполняться быстрее. Это потому, что эта быстрая сортировка обычно быстрее, чем люди используют ее вместо слияния.

Тем не менее! Я лично часто использую сортировку слиянием или вариант быстрой сортировки, которая ухудшается до сортировки слиянием, когда быстрая сортировка работает плохо. Помните. Быстрая сортировка только O (n log n) на в среднем . Это наихудший случай O (n ^ 2)! Mergesort всегда O (n log n). В случаях, когда производительность или скорость реагирования в реальном времени являются обязательными, а ваши входные данные могут поступать из вредоносного источника, не следует использовать простую быструю сортировку.