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

StackOverflow https://stackoverflow.com/questions/70402

Вопрос

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

Это было полезно?

Решение

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

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

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

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

Другие советы

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

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

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

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

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

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

Быстрая сортировка более популярна, потому что она:

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

«и все же большинство людей используют быструю сортировку вместо сортировки слиянием.Почему это?"

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

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

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

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

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

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

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

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

QuickSort также конкурирует с Mergesort, еще одним рекурсивным алгоритмом сортировки, но с преимуществом времени работы θ (Nlogn).Mergesort-это стабильная сортировка, в отличие от QuickSort и Heapsort, и его можно легко адаптировать для работы в связанных списках и очень больших списках, хранящихся в медленном среде, таких как хранение дисков или прикрепленное сетевое хранилище.Хотя QuickSort может быть записан для работы в связанных списках, он часто будет страдать от плохого выбора поворота без случайного доступа.Основным недостатком Mergesort является то, что при работе на массивах требуется вспомогательное пространство θ (n) в лучшем случае, тогда как вариант быстрого сорта с распределением на месте и хлебной рекурсией использует только пространство θ (logn).(Обратите внимание, что при работе в связанных списках Mergesort требует лишь небольшого постоянного количества вспомогательного хранилища.)

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

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

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

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

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

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

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

Объяснение Википедии следующее:

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

Быстрая сортировка

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

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

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

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

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

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

1) Малое количество ключей в данных.Набор данных с одинаковым значением будет сортироваться за n^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-атаке с использованием данных, которые предназначены для выполнения в худшем случае.Современные реализации позволяют избежать этого с помощью различных методов, таких как рандомизация данных перед сортировкой, выбор медианы из трех случайно выбранных индексов и т. д.При такой рандомизации у нас есть 2 случая:

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

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

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

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

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

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

Наша реализация быстрой сортировки остановится на 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 секунду, необходимую для нажатия кнопки [СОРТИРОВАТЬ], примерно в тысячу раз выше, чем для того, чтобы увидеть, как выполняется сортировка 5000 элементов. еще хуже чем 10*идеальный случай.Этот шанс уменьшается по мере увеличения набора данных.Вот некоторые размеры массивов и соответствующие им шансы работать дольше 10*идеально:

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

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

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

Ответ будет слегка склоняться в сторону быстрой сортировки по сравнению с изменениями, внесенными с помощью DualPivotQuickSort для примитивных значений.Он используется в ЯВА 7 сортировать java.util.Массивы 

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 отсортированных подмассива

На верхнем уровне объединение двух отсортированных подмассивов предполагает работу с N элементами.

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

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

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

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

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

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

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

Потом Н-7...Потом Н-15...Потом Н-32...

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

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

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

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

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

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

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

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

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

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

Всегда ли быстрая сортировка лучше сортировки слиянием?

Не совсем.

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

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

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

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

Сортировка слиянием также требует памяти 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%.

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

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

Тем не менее, все сказанное ранее верно:- QuickSort может быть n^2, но Sedgewick утверждает, что у хорошей рандомизированной реализации больше шансов на то, что компьютер будет поражен молнией, чем n^2 - Mergesort требует дополнительного места

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На земле C/C ++, когда я не использую контейнеры STL, я склонен использовать QuickSort, потому что он встроен во время выполнения, а Mergesort - нет.

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top