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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

Answer 4

"и все же большинство людей используют Quicksort вместо Mergesort. Почему это так?"

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

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

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

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

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

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

Answer 9

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

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

Answer 10

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

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

Quicksort

1012 * слияние *

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