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

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

Быстрая сортировка имеет O ( n ² ) времени выполнения в худшем случае и O ( n log n ) среднего времени выполнения. Тем не менее, во многих сценариях предпочтительнее сортировка слиянием, поскольку многие факторы влияют на время выполнения алгоритма, и, собрав их все вместе, выигрывает быстрая сортировка.

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

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

На практике многие современные реализации быстрой сортировки (в частности, libstdc ++ std::sort) фактически являются интросортированными , теоретический наихудший случай которых равен O ( n log n ), так же, как сортировка слиянием. Это достигается путем ограничения глубины рекурсии и переключения на другой алгоритм ( heapsort ), когда он превышает log n .

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

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

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

Кроме того, если вам нужно что- то делать с наборами данных такого размера, подумайте о том, как избежать поиска на диске. Например, именно поэтому это стандартный совет: перед выполнением больших загрузок данных в базы данных отбрасывать индексы, а затем перестраивать индекс позже. Поддержание индекса во время загрузки означает постоянный поиск на диске. Напротив, если вы отбрасываете индексы, то база данных может перестроить индекс, сначала отсортировав информацию, с которой нужно иметь дело (конечно, используя сортировку слиянием!), А затем загрузив ее в структуру данных BTREE для индекса. (BTREEs естественно поддерживаются в порядке, поэтому вы можете загрузить один из отсортированного набора данных с несколькими поисками на диск.)

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

На самом деле QuickSort - это O (n ² ). Его средний случай время работы составляет O (Nlog (п)), но в худшем случае это O (п ² ), которое происходит , когда вы запускаете его в списке , который содержит несколько уникальных предметов. Рандомизация занимает O (n). Конечно, это не меняет наихудшего случая, оно просто предотвращает длительную работу злоумышленника.

QuickSort более популярен, потому что:

1. На месте (MergeSort требует дополнительной памяти, линейной по количеству сортируемых элементов).
2. Имеет небольшую скрытую константу.

«И все же большинство людей используют Quicksort вместо Mergesort. Почему?»

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

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

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

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

Я хотел бы добавить, что из трех упомянутых выше алгоритмов (mergesort, quicksort и heap sort) только mergesort является стабильным. То есть порядок не изменяется для тех значений, которые имеют одинаковый ключ. В некоторых случаях это желательно.

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

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

Из записи Википедии о быстрой сортировке :

Quicksort также конкурирует с mergesort, другим алгоритмом рекурсивной сортировки, но с преимуществом времени выполнения Θ (nlogn) в худшем случае. Mergesort является стабильной сортировкой, в отличие от быстрой сортировки и heapsort, и может быть легко адаптирован для работы со связанными списками и очень большими списками, хранящимися на медленных носителях доступа, таких как дисковое хранилище или сетевое хранилище. Хотя быстрая сортировка может быть написана для работы со связанными списками, она часто страдает от неудачного выбора сводных данных без произвольного доступа. Основным недостатком сортировки слиянием является то, что при работе с массивами в лучшем случае требуется Θ (n) вспомогательного пространства, тогда как вариант быстрой сортировки с разделением на месте и хвостовой рекурсией использует только пространство log (logn). (Обратите внимание, что при работе со связанными списками для сортировки слиянием требуется только небольшой постоянный объем вспомогательного хранилища.)

Му! Быстрая сортировка не лучше, она хорошо подходит для другого вида применения, чем слияние.

Mergesort стоит учитывать, если скорость важна, плохая производительность в худшем случае недопустима и доступно дополнительное пространство. 1

Вы заявили, что они «Они оба O (nlogn) […]». Это не верно. «Quicksort использует около n ^ 2/2 сравнений в худшем случае». 1 .

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

1 Седжвик, Алгоритмы

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

Heapsort гарантированно работает в O (n * ln (n)) и требует только конечного дополнительного хранилища. Но есть много цитат из реальных тестов, которые показывают, что heapsort значительно медленнее, чем quicksort в среднем.

Объяснение Википедии:

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

Quicksort

Сортировка слиянием

Я думаю, что есть также проблемы с объемом памяти, необходимым для Mergesort (то есть Ω (n)), которого нет в реализациях быстрой сортировки. В худшем случае это одинаковое количество алгоритмического времени, но сортировка слиянием требует больше памяти.

Я хотел бы добавить к существующим отличным ответам некоторую математику о том, как 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% pivot-разделов, чтобы разбить входное значение 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], у пользователя примерно в тысячу раз выше, чем у 5 000 элементов, которые работают хуже чем 10 * идеальный случай. Этот шанс уменьшается по мере увеличения набора данных. Вот некоторые размеры массивов и их соответствующие шансы работать дольше 10 * идеально:

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

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

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

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

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

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

На самом деле, нет.

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

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

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

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

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

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

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

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. Я не делал математики, чтобы увидеть, насколько большую роль этот фактор и фактор, описанный выше, на самом деле играют в сложности алгоритма.

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

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

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

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

Трудно сказать. Худший из 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 space. И MergeSort также нужно сделать много копий массива, которые мы не включайте в анализ алгоритма. Одним словом, MergeSort действительно быстрее, чем быстрая сортировка в theroy, но в действительности вам нужно учитывать пространство памяти, стоимость копирования массива, слияние медленнее, чем быстрая сортировка. Однажды я сделал эксперимент, в котором мне дали 1000000 цифр в Java классом Random,и потребовалось 2610мс для сортировки слиянием, 1370мс для быстрой сортировки.

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

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

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

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

[5, 4, 3, 2, 1]

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

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

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

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

1- Вспомогательное пространство: быстрая сортировка - это алгоритм сортировки на месте. Сортировка на месте означает, что для выполнения сортировки не требуется дополнительное место для хранения. С другой стороны, сортировка слиянием требует временного массива для объединения отсортированных массивов, и, следовательно, он не на месте.

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

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

4- Хвостовая рекурсия: QuickSort является хвостовой рекурсией, а сортировка Merge - нет. Хвостовая рекурсивная функция - это функция, где рекурсивный вызов - это последнее, что выполняется функцией. Хвостовые рекурсивные функции считаются лучше, чем хвостовые рекурсивные функции, поскольку хвостовая рекурсия может быть оптимизирована компилятором.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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