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

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

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

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

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

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

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

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

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

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

Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case Θ(nlogn) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that, when operating on arrays, it requires Θ(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only Θ(logn) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)

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

Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the probability of requiring quadratic time.

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

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

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

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

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

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

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

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

Му! Quicksort не лучше, чем mergesort, он больше подходит для других приложений.

Mergesort is worth considering if speed is of the essence, bad worst-case performance cannot be tolerated, and extra space is available.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Трудно сказать. Худший из MergeSort - это n (log2n) -n + 1, что верно, если n равно 2 ^ k (я уже доказал это). И для любого n это между (n lg n - n + 1) и (n lg n + n + O (lg n)). Но для quickSort лучше всего nlog2n (также n равно 2 ^ k). Если вы разделите Mergesort на quickSort, он будет равен единице, когда n бесконечно. это как если бы наихудший вариант MergeSort лучше, чем лучший вариант QuickSort, почему мы используем быструю сортировку? Но помните, что MergeSort не на месте, для этого требуется 2n мемройского пространства. не включайте в анализ алгоритма. Одним словом, MergeSort действительно быстрее, чем быстрая сортировка, но на самом деле вам нужно учитывать пространство памяти, стоимость копирования массива, слияние происходит медленнее, чем быстрая сортировка. Я однажды сделал эксперимент, в котором мне дали 1000000 цифр в java классом Random, и потребовалось 2610 мс при сортировке слиянием, 1370 мс при быстрой сортировке.

Ответ был бы слегка склонен к быстрой сортировке по отношению к изменениям, внесенным с помощью 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 ^ 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. На основе этой вероятности быстрая сортировка эффективна для среднего (и типичного) случая.

Чем хорош Quicksort?

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

Всегда ли Quicksort лучше Mergesort?

Не совсем.

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

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

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

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

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

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

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

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

1. Сортировать левый подмассив
2. Сортировать правый подмассив
3. Объедините 2 отсортированных подмассива

На верхнем уровне слияние 2 отсортированных подмассивов включает работу с N элементами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обновлено: я только что обнаружил, что худший / лучший / средний случай сортировки слиянием всегда nlogn, но быстрая сортировка может варьироваться от n2 (худший случай, когда элементы уже отсортированы) до nlogn (avg / лучший случай, когда pivot всегда делит массив на два половинки).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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