Почему быстрая сортировка лучше, чем слияние?
Мне задавали этот вопрос во время интервью. Они оба O(nlogn), и все же большинство людей используют Quicksort вместо Mergesort. Это почему?
28 ответов
Быстрая сортировка имеет O (n2) времени выполнения в худшем случае и O (n logn) среднего времени выполнения. Тем не менее, во многих сценариях предпочтительнее сортировка слиянием, поскольку многие факторы влияют на время выполнения алгоритма, и при их объединении быстрая сортировка выигрывает.
В частности, часто цитируемое время выполнения алгоритмов сортировки относится к числу сравнений или количеству перестановок, необходимых для сортировки данных. Это действительно хороший показатель производительности, тем более что он не зависит от базовой аппаратной конструкции. Тем не менее, другие вещи, такие как локальность ссылок (то есть, мы читаем много элементов, которые, вероятно, находятся в кеше?), Также играют важную роль на современном оборудовании. В частности, для быстрой сортировки требуется мало дополнительного пространства, и она имеет хорошую локальность кэша, что во многих случаях делает это быстрее, чем сортировка слиянием.
Кроме того, очень легко избежать наихудшего времени выполнения быстрой сортировки O (n2) почти полностью, используя соответствующий выбор точки поворота - например, случайный выбор (это отличная стратегия).
На практике многие современные реализации быстрой сортировки (в частности, libstdC++'s std::sort) на самом деле являются интросортами, теоретический наихудший случай которых равен O (n logn), так же, как сортировка слиянием. Это достигается путем ограничения глубины рекурсии и переключения на другой алгоритм ( heapsort), когда он превышает logn.
Как отмечали многие люди, средняя производительность для быстрой сортировки быстрее, чем для сортировки слиянием. Но это верно только в том случае, если вы предполагаете постоянное время для доступа к любому фрагменту памяти по требованию.
В оперативной памяти это предположение обычно не так уж плохо (оно не всегда верно из-за кешей, но это не так уж плохо). Однако, если ваша структура данных достаточно велика, чтобы жить на диске, то быстрая сортировка убивается тем фактом, что ваш средний диск выполняет примерно 200 случайных операций поиска в секунду. Но этот же диск не имеет проблем при последовательном чтении или записи мегабайт в секунду данных. Именно это и делает Mergesort.
Поэтому, если данные должны быть отсортированы на диске, вам действительно нужно использовать некоторые варианты сортировки слиянием. (Обычно вы быстро сортируете подсписки, а затем начинаете объединять их вместе, превышая некоторый порог размера.)
Кроме того, если вам нужно что- то делать с наборами данных такого размера, подумайте о том, как избежать поиска на диске. Например, именно поэтому это стандартный совет: перед выполнением больших загрузок данных в базы данных отбрасывать индексы, а затем перестраивать индекс позже. Поддержание индекса во время загрузки означает постоянный поиск на диске. Напротив, если вы отбрасываете индексы, то база данных может перестроить индекс, сначала отсортировав информацию, с которой нужно иметь дело (конечно, используя сортировку слиянием!), А затем загрузив ее в структуру данных BTREE для индекса. (BTREEs естественно поддерживаются в порядке, поэтому вы можете загрузить один из отсортированного набора данных с несколькими поисками на диск.)
Был ряд случаев, когда понимание того, как избежать поиска диска, позволило мне сделать работу по обработке данных часами, а не днями или неделями.
На самом деле QuickSort - это O (n2). Среднее время его выполнения - O (nlog (n)), а наихудшим - O (n2), которое возникает, когда вы запускаете его в списке, содержащем несколько уникальных элементов. Рандомизация занимает O (n). Конечно, это не меняет худшего случая, оно просто предотвращает длительную работу злоумышленника.
QuickSort более популярен, потому что:
- На месте (MergeSort требует дополнительной памяти, линейной по количеству сортируемых элементов).
- Имеет небольшую скрытую константу.
Анимированные алгоритмы сортировки показывают ряд алгоритмов для 4 различных начальных условий (случайные, почти отсортированные, обратные, мало уникальных) и могут помочь.
"И все же большинство людей используют Quicksort вместо Mergesort. Почему?"
Одна психологическая причина, которая не была дана, состоит в том, что Quicksort назван более умно. т.е. хороший маркетинг.
Да, быстрая сортировка с тройным разделением, вероятно, является одним из лучших алгоритмов сортировки общего назначения, но при этом нельзя упускать из виду тот факт, что "быстрая" сортировка звучит гораздо более мощно, чем сортировка "слияние".
Как отмечали другие, наихудший случай быстрой сортировки - O(n^2), тогда как сортировка слиянием и heapsort остаются в точке O(nlogn). Однако в среднем случае все три являются O(nlogn); поэтому они в подавляющем большинстве случаев сопоставимы.
Что делает Quicksort лучше в среднем, так это то, что внутренний цикл подразумевает сравнение нескольких значений с одним, в то время как для двух других оба термина различны для каждого сравнения. Другими словами, Quicksort выполняет вдвое меньше операций чтения, чем два других алгоритма. На современных процессорах производительность сильно зависит от времени доступа, поэтому в итоге Quicksort станет отличным выбором.
Это частый вопрос, который задают в интервью, что, несмотря на лучшую производительность сортировки слиянием в худшем случае, быстрая сортировка считается лучше, чем сортировка слиянием, особенно для больших входных данных. Есть определенные причины, по которым быстрая сортировка лучше:
1- Вспомогательное пространство: быстрая сортировка - это алгоритм сортировки на месте. Сортировка на месте означает, что для выполнения сортировки не требуется дополнительное пространство для хранения. Сортировка слиянием, с другой стороны, требует временного массива для объединения отсортированных массивов, и, следовательно, он не на месте.
2- Худший случай: худший случай быстрой сортировкиO(n^2)можно избежать, используя рандомизированную быструю сортировку. Этого легко можно избежать с большой вероятностью, выбрав правильный стержень. Получение поведения усредненного кейса путем выбора правильного элемента сводки позволяет улучшить производительность и стать таким же эффективным, как сортировка слиянием.
3- Местоположение ссылки: Quicksort, в частности, демонстрирует хорошую локальность кеша, и это делает его быстрее, чем сортировка слиянием во многих случаях, например, в среде виртуальной памяти.
4- Хвостовая рекурсия: QuickSort является хвостовой рекурсией, а сортировка слиянием - нет. Хвостовая рекурсивная функция - это функция, в которой рекурсивный вызов - это последнее, что выполняет функция. Хвостовые рекурсивные функции считаются лучше, чем нехвостовые рекурсивные функции, поскольку хвостовая рекурсия может быть оптимизирована компилятором.
Я хотел бы добавить, что из трех упомянутых выше алгоритмов (mergesort, quicksort и heap sort) только mergesort является стабильным. То есть порядок не изменяется для тех значений, которые имеют одинаковый ключ. В некоторых случаях это желательно.
Но, по правде говоря, большинству людей нужна только хорошая средняя производительность, а быстрая сортировка... быстрая =)
Все алгоритмы сортировки имеют свои взлеты и падения. См. Статью Wikipedia для алгоритмов сортировки для хорошего обзора.
Му! Быстрая сортировка не лучше, она хорошо подходит для другого вида применения, чем слияние.
Mergesort стоит учитывать, если скорость важна, плохая производительность в худшем случае не может быть допущена, и имеется дополнительное пространство. 1
Вы заявили, что они "Они оба O(nlogn) […]". Это не верно. "Quicksort использует около n^2/2 сравнений в худшем случае." 1.
Однако, по моему опыту, наиболее важным свойством является простота реализации последовательного доступа, который вы можете использовать при сортировке при использовании языков программирования с императивной парадигмой.
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 консервативных (и ложных) предположения для упрощения математики:
Хорошие точки разворота всегда точно на 25%/75% и работают в 2,4* идеальном случае. Мы никогда не получим идеальное разделение или любое разделение лучше, чем 25/75.
Плохие точки всегда являются наихудшим случаем и, по сути, не способствуют решению проблемы.
Наша реализация 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 секунды, необходимого для нажатия кнопки [СОРТ], у вашего пользователя примерно в тысячу раз выше, чем у 5 000 элементов, которые работают хуже чем 10 * идеальный случай. Этот шанс уменьшается по мере увеличения набора данных. Вот некоторые размеры массивов и их соответствующие шансы работать дольше 10 * идеально:
- Массив из 640 предметов: 10^-13 (требуется 15 хороших точек разворота из 60 попыток)
- Массив из 5000 элементов: 10^-18 (требуется 22 хороших пивота из 88 попыток)
- Массив из 40000 элементов:10^-23 (требуется 29 хороших опорных точек из 116)
Помните, что это с двумя консервативными предположениями, которые хуже, чем реальность. Таким образом, фактическая производительность еще лучше, а баланс оставшейся вероятности ближе к идеалу, чем нет.
Наконец, как уже упоминали другие, даже эти нелепо маловероятные случаи можно устранить, переключившись на сортировку кучи, если стек рекурсии заходит слишком глубоко. Таким образом, TLDR заключается в том, что для хороших реализаций QuickSort наихудшего случая на самом деле не существует, поскольку он был спроектирован и выполнение завершается за O(n*logn) времени.
Из записи Википедии о быстрой сортировке:
Быстрая сортировка также конкурирует с mergesort, другим алгоритмом рекурсивной сортировки, но с преимуществом времени выполнения worst (nlogn) в худшем случае. Mergesort является стабильной сортировкой, в отличие от быстрой сортировки и heapsort, и может быть легко адаптирован для работы со связанными списками и очень большими списками, хранящимися на медленных носителях доступа, таких как дисковое хранилище или сетевое хранилище. Хотя быстрая сортировка может быть написана для работы со связанными списками, она часто страдает от неудачного выбора сводной области без произвольного доступа. Основным недостатком сортировки слиянием является то, что при работе с массивами в лучшем случае требуется Θ(n) вспомогательного пространства, тогда как вариант быстрой сортировки с разделением на месте и хвостовой рекурсией использует только пространство log (logn). (Обратите внимание, что при работе со связанными списками для сортировки слиянием требуется только небольшой постоянный объем вспомогательного хранилища.)
Быстрая сортировка НЕ лучше, чем слияние. С O(n^2) (наихудший случай, который редко случается), быстрая сортировка потенциально намного медленнее, чем O(nlogn) сортировки слиянием. Quicksort имеет меньше накладных расходов, поэтому с маленькими и медленными компьютерами это лучше. Но компьютеры сегодня настолько быстры, что дополнительные издержки сортировки слиянием незначительны, и риск очень медленной быстрой сортировки значительно превышает незначительные издержки сортировки слиянием в большинстве случаев.
Кроме того, сортировка слиянием оставляет элементы с одинаковыми ключами в их первоначальном порядке полезным атрибутом.
Быстрая сортировка является самым быстрым алгоритмом сортировки на практике, но имеет ряд патологических случаев, которые могут заставить его работать так же плохо, как O (n2).
Heapsort гарантированно работает в O(n*ln(n)) и требует только конечного дополнительного хранилища. Но есть много цитат из реальных тестов, которые показывают, что heapsort значительно медленнее, чем quicksort в среднем.
Объяснение Википедии:
Как правило, быстрая сортировка на практике значительно быстрее, чем другие алгоритмы Θ(nlogn), потому что ее внутренний цикл может быть эффективно реализован на большинстве архитектур, а в большинстве реальных данных можно сделать выбор проекта, который минимизирует вероятность необходимости квадратичного времени.,
Я думаю, что есть также проблемы с объемом памяти, необходимым для Mergesort (то есть Ω(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 требует дополнительного места
В отличие от сортировки слиянием, быстрая сортировка не использует вспомогательное пространство. В то время как сортировка слиянием использует вспомогательное пространство O(n). Но сортировка слиянием имеет наихудшую временную сложность O(nlogn), тогда как наихудшая сложность быстрой сортировки - O(n^2), которая происходит, когда массив уже отсортирован.
Почему быстрая сортировка хороша?
- QuickSort занимает N^2 в худшем случае и NlogN в среднем. Худший случай происходит, когда данные отсортированы. Это может быть смягчено случайным перемешиванием перед началом сортировки.
- Быстрая сортировка не требует дополнительной памяти, занимаемой сортировкой слиянием.
- Если набор данных большой и в нем присутствуют идентичные элементы, сложность быстрой сортировки уменьшается с помощью трехстороннего разделения. Больше нет идентичных предметов, лучше сортировка. Если все элементы идентичны, они сортируются по линейному времени. [Это реализация по умолчанию в большинстве библиотек]
Всегда ли Quicksort лучше, чем Mergesort?
На самом деле, нет.
- Mergesort стабилен, а Quicksort - нет. Так что если вам нужна стабильность в выводе, вы должны использовать Mergesort. Стабильность требуется во многих практических применениях.
- Память дешевая в наше время. Поэтому, если дополнительная память, используемая Mergesort, не критична для вашего приложения, использование Mergesort не повредит.
Примечание. В java функция Arrays.sort() использует Quicksort для примитивных типов данных и Mergesort для типов данных объектов. Поскольку объекты потребляют служебную память, поэтому добавленные небольшие накладные расходы для Mergesort могут не представлять проблемы с точки зрения производительности.
Ссылка: Посмотрите видео QuickSort 3-й недели, курс алгоритмов Принстона на Coursera
В сортировке слиянием общий алгоритм:
- Сортировка левого подмассива
- Сортировать правильный под-массив
- Объединить 2 отсортированных подмассива
На верхнем уровне объединение 2 отсортированных подмассивов включает в себя работу с N элементами.
На один уровень ниже, каждая итерация шага 3 включает в себя работу с N/2 элементами, но вы должны повторить этот процесс дважды. Таким образом, вы по-прежнему имеете дело с 2 * N/2 == N элементами.
На один уровень ниже, вы объединяете 4 * N/4 == N элементов и так далее. Каждая глубина в рекурсивном стеке включает в себя объединение одинакового количества элементов во всех вызовах для этой глубины.
Вместо этого рассмотрим алгоритм быстрой сортировки:
- Выберите опорную точку
- Поместите точку поворота в правильном месте в массиве, все меньшие элементы слева, а более крупные элементы справа
- Сортировать левый подмассив
- Сортировать правый подмассив
На верхнем уровне вы имеете дело с массивом размера 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. Я не делал математики, чтобы увидеть, насколько большую роль этот фактор и фактор, описанный выше, на самом деле играют в сложности алгоритма.
Ответ будет слегка наклонен в сторону быстрой сортировки по отношению к изменениям, внесенным с помощью 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
Хотя они оба находятся в одном классе сложности, это не значит, что они оба имеют одинаковое время выполнения. Быстрая сортировка обычно быстрее, чем сортировка слиянием, просто потому, что проще кодировать жесткую реализацию, и выполняемые ею операции могут выполняться быстрее. Это происходит потому, что обычно быстрая сортировка быстрее, чем люди используют ее вместо слияния.
Тем не мение! Я лично часто использую сортировку слиянием или вариант быстрой сортировки, которая ухудшается до сортировки слиянием, когда быстрая сортировка работает плохо. Помните. Быстрая сортировка составляет в среднем только O(n log n). Это наихудший случай O(n^2)! Mergesort всегда O(n log n). В случаях, когда производительность или скорость реагирования в реальном времени являются обязательными и ваши входные данные могут поступать из злонамеренного источника, вы не должны использовать простую быструю сортировку.
Быстрая сортировка имеет среднюю сложность, но в некоторых приложениях это неправильный выбор. Быстрая сортировка уязвима для атак отказа в обслуживании. Если злоумышленник может выбрать входные данные для сортировки, он может легко создать набор, который принимает сложность времени наихудшего случая o(n^2).
Средняя сложность Mergesort и сложность наихудшего случая одинаковы, и, как таковая, не сталкивается с одной и той же проблемой. Это свойство сортировки слиянием также делает его лучшим выбором для систем реального времени - именно потому, что нет патологических случаев, которые заставляют его работать намного, намного медленнее.
По этим причинам я больше поклонник Mergesort, чем Quicksort.
Быстрая сортировка - наихудший случай 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. На основании этой вероятности быстрая сортировка эффективна для среднего (и типичного) случая.
Трудно сказать. Худший из 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 мс с помощью быстрой сортировки.
Когда я экспериментировал с обоими алгоритмами сортировки, подсчитывая количество рекурсивных вызовов, быстрая сортировка последовательно имела меньше рекурсивных вызовов, чем сортировка слиянием. Это связано с тем, что у быстрой сортировки есть точки, а точки не включаются в следующие рекурсивные вызовы. Таким образом, быстрая сортировка может достичь рекурсивного базового случая быстрее, чем сортировка слиянием.
Небольшие дополнения к быстрой сортировке против слияния.
Также это может зависеть от вида сортировки предметов. Если доступ к элементам, обмен и сравнение не являются простыми операциями, такими как сравнение целых чисел в плоской памяти, тогда сортировка слиянием может быть предпочтительным алгоритмом.
Например, мы сортируем элементы по сетевому протоколу на удаленном сервере.
Кроме того, в пользовательских контейнерах, таких как "связанный список", быстрая сортировка не дает никаких преимуществ.
1. Объединить сортировку в связанном списке, не нужно дополнительной памяти.
2. Доступ к элементам в быстрой сортировке не последовательный (в памяти)
Что-то, чтобы рассмотреть также память. Mergesort требует дополнительного массива, скажем, "массива рабочего пространства". Если ваша память едва достаточна для хранения исходного массива, сортировка слиянием не будет работать.
При прочих равных условиях я бы ожидал, что большинство людей будут использовать все, что наиболее удобно, и это будет qsort(3). Кроме этой быстрой сортировки известно, что она очень быстро работает с массивами, точно так же как mergesort является обычным выбором для списков.
Что меня интересует, так это то, почему так редко можно увидеть корень или ковш. Они O(n), по крайней мере, в связанных списках, и все, что нужно, это какой-то метод преобразования ключа в порядковое число. (Строки и поплавки работают просто отлично.)
Я думаю, причина в том, как преподается информатика. Мне даже пришлось продемонстрировать моему лектору по анализу алгоритмов, что действительно возможно сортировать быстрее, чем O(n log(n)). (У него было доказательство того, что нельзя сравнивать сортировку быстрее, чем O(n log(n)), что верно.)
В других новостях числа с плавающей точкой могут быть отсортированы как целые числа, но вы должны повернуть отрицательные числа потом.
Изменить: На самом деле, вот еще более порочный способ сортировки чисел с плавающей точкой: http://www.stereopsis.com/radix.html. Обратите внимание, что трюк с переключением битов можно использовать независимо от того, какой алгоритм сортировки вы на самом деле используете...
Учитывайте сложность времени и пространства. Для сортировки слиянием: Сложность времени: O (nlogn), Сложность пространства: O (nlogn)
Для быстрой сортировки: сложность времени: O(n^2), сложность пространства: O (n)
Теперь они оба выигрывают по одному сценарию каждый. Но, используя случайную опору, вы почти всегда можете уменьшить сложность времени быстрой сортировки до O(nlogn).
Таким образом, быстрая сортировка предпочтительна во многих приложениях, а не сортировка слиянием.
Быстрая сортировка является алгоритмом сортировки на месте, поэтому она лучше подходит для массивов. С другой стороны, сортировка слиянием требует дополнительного хранения O(N) и больше подходит для связанных списков.
В отличие от массивов, в список избранного мы можем вставлять элементы посередине с пробелом O(1) и временем O(1), поэтому операция слияния в сортировке слиянием может быть реализована без лишних пробелов. Однако выделение и отмена выделения дополнительного пространства для массивов отрицательно влияет на время выполнения сортировки слиянием. Сортировка слиянием также поддерживает связанный список, поскольку к данным обращаются последовательно, без особого произвольного доступа к памяти.
С другой стороны, быстрая сортировка требует большого количества произвольного доступа к памяти, а с помощью массива мы можем напрямую обращаться к памяти без какого-либо обхода, как того требуют связанные списки. Кроме того, быстрая сортировка при использовании для массивов имеет хорошее месторасположение, поскольку массивы хранятся в памяти непрерывно.
Несмотря на то, что средняя сложность обоих алгоритмов сортировки равна O(NlogN), обычно люди для обычных задач используют массив для хранения, и по этой причине быстрая сортировка должна быть предпочтительным алгоритмом.
РЕДАКТИРОВАТЬ: я только что обнаружил, что сортировка слиянием худший / лучший / средний случай всегда nlogn, но быстрая сортировка может варьироваться от n2(худший случай, когда элементы уже отсортированы) до nlogn(avg/ лучший случай, когда сводка всегда делит массив на два половинки).
В земле c/ C++, когда не используются контейнеры stl, я склонен использовать быструю сортировку, потому что она встроена во время выполнения, а слияние - нет.
Поэтому я считаю, что во многих случаях это просто путь наименьшего сопротивления.
Кроме того, при быстрой сортировке производительность может быть намного выше, если весь набор данных не помещается в рабочий набор.