Почему quicksort лучше, чем сортировка с объединением?

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

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

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

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

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

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

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

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

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

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

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

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

я - более крупный поклонник Сортировки с объединением, чем я имею Quicksort по этим причинам.

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

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

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

, Кроме того, если необходимо сделать что-нибудь с наборами данных того размера, думайте трудно о том, как избежать, ищет на диск. Например, это - то, почему это - стандартный совет, что Вы отбрасываете индексы прежде, чем сделать большие загрузки данных в базах данных, и затем восстанавливаете индекс позже. Поддержание индекса во время загрузки постоянно означает ищущий на диск. В отличие от этого, при отбрасывании индексов тогда база данных может восстановить индекс первой сортировкой информации, с которой будут иметь дело с (использование сортировки с объединением, конечно!) и затем загрузка его в B-ДЕРЕВО datastructure для индекса. (B-ДЕРЕВЬЯ естественно поддерживаются в порядке, таким образом, можно загрузиться один от отсортированного набора данных с немногими, ищет на диск.)

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

На самом деле QuickSort является O (n <глоток> 2 ). средний случай время выполнения является O (nlog (n)), но худший случай является O (n <глоток> 2 ), который происходит, когда Вы выполняете его в списке, который содержит немного уникальных объектов. Рандомизация берет O (n). Конечно, это не изменяет его худший случай, это просто препятствует тому, чтобы злонамеренный пользователь заставил Ваш вид занять много времени.

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

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

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

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

От статья в Википедии о Quicksort:

Quicksort также конкурирует с сортировкой с объединением, другим рекурсивным алгоритмом сортировки, но с преимуществом худшего случая О ˜ (nlogn) время выполнения. Сортировка с объединением является стабильным видом, в отличие от quicksort и пирамидальной сортировки, и может быть легко адаптирована для работы на связанные списки и очень большие списки, сохраненные на медиа не-спешащего-доступа, таких как память на диске или сетевое хранилище данных. Хотя quicksort может быть записан для работы на связанные списки, он будет часто страдать от плохого выбора центра без произвольного доступа. Основной недостаток сортировки с объединением - то, что при работе на массивы она требует О ˜ (n) вспомогательное пространство в лучшем случае, тогда как вариант quicksort с оперативным разделением и хвостовой рекурсией использует только О ˜ (logn) пространство. (Обратите внимание, что при работе на связанные списки, сортируйте с объединением, только требует небольшой, постоянной суммы вспомогательного устройства хранения данных.)

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

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

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

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

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

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

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

Сортировка с объединением Quicksort

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

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

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

мышиная единица! Quicksort не лучше, он хорошо подходит для другого вида приложения, чем сортировка с объединением.

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

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

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

1 Sedgewick, Алгоритмы

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

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

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