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

cs.stackexchange https://cs.stackexchange.com/questions/3

  •  15-10-2019
  •  | 
  •  

Вопрос

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

После беглого взгляда на еще несколько сеансов естественно сказать , что быстрая сортировка не следует будьте так же эффективны, как и другие.

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

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

Обновление 1: канонический ответ гласит, что константы, задействованные в $ O (n \ log n) $ среднего случая, меньше, чем константы, задействованные в других $ O (n \ log n) $ алгоритмах.Однако я еще не видел надлежащего обоснования этого, с точными расчетами, а не только с интуитивными идеями.

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

Обновление 2: Существует несколько веб-страниц, предлагающих сравнение алгоритмов сортировки, некоторые из которых более причудливы, чем другие (наиболее примечательны sorting-algorithms.com).Помимо представления хорошего наглядного пособия, такой подход не дает ответа на мой вопрос.

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

Решение

Короткий ответ

Аргумент эффективности кэша уже подробно объясняется. Кроме того, существует внутренний аргумент, почему QuickSort быстро. При реализации как с двумя «пересеченными указателями», Например, внутренние петли имеют очень маленькое тело. Поскольку это выполняется код чаще всего, это окупается.

Длинный ответ

Прежде всего,

А Средний случай не существует!

Как наилучшим и худшим случаем, часто встречаются крайне редко на практике, анализ среднего случая проводится. Но любой средний анализ случая предполагает некоторые Распределение входов! Для сортировки типичный выбор - это Случайная модель перестановки (молчаливо предполагается в Википедии).

Почему $ $-Notation?

Отбрасывание констант при анализе алгоритмов осуществляется по одной основной причине: если я заинтересован в точный время бега, Мне нужны (относительно) затраты на все заинтересованные базовые операции (Даже все еще игнорируя проблемы кэширования, трубопроводы в современных процессорах ...). Математический анализ может считать Как часто каждая инструкция выполняется, но время работы отдельных инструкций зависят от деталей процессора, например, требует ли 32-разрядное целочисленное умножение, а также добавление.

Есть два пути:

  1. Исправьте какую -то машинную модель.

    Это делается в доне КнутСерия книг «Искусство компьютерного программирования» Для искусственного «типичного» компьютера, изобретенного автором. В томе 3 вы найдете точное Средние результаты случая Для многих алгоритмов сортировки, например

    • QuickSort: $ 11,667 (n+1) ln (n) -1,74n-18,74 $
    • Mergesort: $ 12,5 N ln (n) $
    • Heapsort: $ 16 n ln (n) +0,01n $
    • Вставка: $ 2,25N^2+7,75N-3LN (n) $Runtimes of several sorting algorithms
      [источник]

    Эти результаты показывают, что QuickSort является самым быстрым. Но это доказано только на искусственной машине Кнута, она не обязательно подразумевает что -либо для того, чтобы сказать ваш x86 PC. Также обратите внимание, что алгоритмы по -разному связаны с небольшими входами:
    Runtimes of several sorting algorithms for small inputs
    [источник]

  2. Анализировать абстрактный Основные операции.

    Для сортировки на основе сравнения это обычно замены а также Ключевые сравнения. Анкет В книгах Роберта Седжвика, например «Алгоритмы», этот подход преследуется. Вы найдете там

    • QuickSort: 2n ln (n) $ сравнения и $ frac13n ln (n) $ в среднем.
    • Mergesort: $ 1,44N ln (n) $ сравнения, но до 8,66 н.
    • Вставка: $ frac14n^2 $ сравнения и $ frac14n^2 $ в среднем.

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

Другие входные распределения

Как отмечалось выше, средние случаи всегда связаны с некоторым входным распределением, поэтому можно рассмотреть другие, кроме случайных перестановок. Например, исследование было сделано для QuickSort с равными элементами И есть хорошая статья о Стандартная функция сортировки в Java

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

Есть несколько замечаний, которые можно высказать по этому вопросу.

Быстрая сортировка обычно происходит быстро

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

В частности, даже если мы выберем pivot, который создает разделение на 10%-90% каждые 10 разделений (что является разделением meh), и разделение на 1 элемент - $ n-1 $ элемент в противном случае (что является наихудшим разделением, которое вы можете получить), наше время выполнения все равно составит $ O (n \ log n) $ (обратите внимание, что это увеличило бы константы до такой степени, что сортировка слиянием, вероятно, будет быстрее).

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

Быстрая сортировка обычно выполняется быстрее, чем сортировки, которые медленнее, чем $ O (n \ log n) $ (скажем, сортировка при вставке с ее временем выполнения $ O (n ^ 2) $), просто потому, что при больших $ n $ их время выполнения увеличивается.

Веская причина, по которой быстрая сортировка выполняется так быстро на практике по сравнению с большинством других алгоритмов $ O (n \ log n) $, таких как Heapsort, заключается в том, что она относительно эффективна при кэшировании.Его время выполнения на самом деле равно $ O (\ frac {n} {B} \log (\ frac {n} {B})) $, где $ B $ - размер блока.Heapsort, с другой стороны, не имеет такого ускорения:это вовсе не обеспечивает эффективный доступ к кешу памяти.

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

Эффективность кэширования могла бы быть дополнительно повышена до $ O(\ frac {n} {B} \log_{\ frac {M} {B}} (\ frac {n} {B})) $, где $ M $ - размер нашей основной памяти, если мы используем быструю сортировку по принципу $ k $.Обратите внимание, что Mergesort также обладает той же эффективностью кэширования, что и Quicksort, и его версия k-way фактически обладает лучшей производительностью (за счет более низких постоянных коэффициентов), если память сильно ограничена.Это подводит к следующему пункту:нам нужно будет сравнить Быструю сортировку с сортировкой слиянием по другим факторам.

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

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

Обратите внимание, что быстрая сортировка будет выполнять больше рекурсивных вызовов, но выделение места в стеке обходится дешево (фактически почти бесплатно, если вы не уничтожаете стек), и вы используете его повторно.Выделение гигантского блока в куче (или на вашем жестком диске, если $ n $ равно в самом деле large) немного дороже, но оба являются накладными расходами в размере $ O (\ log n) $, которые бледнеют по сравнению с работой в размере $ O (n) $, упомянутой выше.

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

Используйте тот сорт, который соответствует вашим потребностям

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

В одном из учебных пособий по программированию в моем университете мы попросили студентов сравнить производительность QuickSort, Mergesort, Sort Sort Vs. Python. Тимскорт) Экспериментальные результаты удивили меня глубоко со времен встроенного списка. Сорт показал намного лучше, чем другие алгоритмы сортировки, даже с случаями, которые легко сделали QuickSort, Mergesort Crash. Таким образом, преждевременно сделать вывод, что обычная реализация QuickSort является лучшей на практике. Но я уверен, что есть гораздо лучшая реализация QuickSort или какую -то гибридную версию.

Это хорошая статья в блоге от Дэвид Р. Макивер Объяснение Тимскорта как форму адаптивного смеси.

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

Таким образом, когда вы начинаете, вы получаете доступ к первым элементам в массиве, и кусок памяти («местоположение») загружается в кеш. И когда вы пытаетесь получить доступ ко второму элементу, это (скорее всего) уже в кэше, так что это очень быстро.

Другие алгоритмы, такие как Heapsort, не работают так, они много прыгают в массиве, что делает их медленными.

Другие уже сказали, что асимптотическое средний Время выполнения QuickSort лучше (в постоянной), чем в других алгоритмах сортировки (в определенных настройках).

Что это значит? Предположим, что любая перестановка выбирается случайным образом (при условии равномерного распределения). В этом случае типичные методы выбора поворота предоставляют поворот, которые В ожидании Разделите список/массив примерно пополам; Это то, что сводит нас к $ cal {o} (n log n) $. Но, кроме того, слияние Частичные решения, полученные путем рецирнирования, занимает только постоянное время (в отличие от линейного времени в случае Mergesort). Конечно, разделение ввода в двух списках в соответствии с Pivot находится в линейное время, но часто требуется мало фактических изменений.

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

Еще один факт, который стоит отметить, заключается в том, что QuickSort медленный На коротких входах по сравнению с алгоритмами SIMPER с меньшим количеством накладных расходов. Следовательно, хорошие библиотеки не вспоминаются до списков длины первой, но будут использовать (например) сортировку вставки, если длина ввода меньше, чем около $ k aox 10 $.

По сравнению с другими алгоритмами сортировки на основе сравнения с сложностью времени $ o (n lg n) $, часто считается лучше, чем другие алгоритмы, такие как Merge-Sort, потому что это алгоритм сортировки на месте. Другими словами, нам не нужна (гораздо больше) память, чтобы хранить членов массива.

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

Смотрите также:

Несмотря на то, что Quick-Sort имеет худшее время работы $ theta (n^2) $, QuickSort считается лучшей сортировкой, потому что в среднем она очень эффективна: его ожидаемое время выполнения-$ theta (n log n ) $, где константы очень малы по сравнению с другими алгоритмами сортировки. Это главная причина использования быстрой сортировки по другим алгоритмам сортировки.

Вторая причина в том, что он работает in-place Сортировка и очень хорошо работает с средами виртуальной памяти.

ОБНОВИТЬ: : (После комментариев Янамы и Свика)

Чтобы проиллюстрировать это лучше, позвольте мне привести пример, используя сортировку Merge (потому что сортировка Merge является следующим широко принятым алгоритмом сортировки после быстрой сортировки) и сообщите вам, откуда берутся дополнительные константы (насколько мне известно и почему я думаю Быстрый сортинг лучше):

Рассмотрим следующее сентяжное:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Если вы все равно посмотрите, как происходит последняя стадия, первые 12 сравниваются с 8 и 8 меньше, так что это идет первым. Теперь 12 снова сравниваются с 21 и 12 идут дальше и так далее и т. Д. Если вы возьмете окончательное слияние, т.е. 4 элемента с 4 другими элементами, он включает в себя много дополнительных сравнений в качестве константы, которые не возникают в быстром роде. Это причина, по которой быстрая сортировка предпочтительнее.

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

Еще в 2008 году я отслеживал висящую программную ошибку до использования QuickSort. Через некоторое время я написал простые имплантации вставки, Quicksort, Heap Sort и слияние сортировки и протестировал их. Моя сортировка слияния превзошла все остальные, работая над большими наборами данных.

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

Во многих случаях я обнаруживал, что самостоятельно думала, что данная реализация работает на удивительно хорошо для QuickSort только для того, чтобы узнать, что на самом деле это не QuickSort. Иногда реализация переключается между QuickSort и другим алгоритмом, а иногда вообще не использует QuickSort. В качестве примера, функции QSORT () Glibc фактически используют сортировку Merge. Только если распределение рабочего пространства не удалось, возвращается к Quicksort на месте. который в комментарии кода называет «Алгоритм более медленного» ».

РЕДАКТИРОВАТЬ: Языки программирования, такие как Java, Python и Perl, также используют сортировку слияния, или, точнее, производное, такое как Timsort или Serge Sort для больших наборов и сортировки вставки для небольших наборов. (Java также использует Quicksort с двумя булочками, который быстрее, чем простой QuickSort.)

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

2 - Быстрый сортинг легче реализовать, чем другие эффективные алгоритмы сортировки.

3 - Быстрый сортирование имеет меньшие постоянные факторы в его время выполнения, чем другие эффективные алгоритмы сортировки.

Обновление: для сортировки слияния вам нужно сделать «слияние», которое требует дополнительных массивов для хранения данных перед слиянием; Но в быстром роде вы этого не делаете. Вот почему быстрая сортировка на месте. Есть также некоторые дополнительные сравнения, сделанные для слияния, которые увеличивают постоянные факторы в сортировке слияния.

При каких условиях конкретный алгоритм сортировки на самом деле является самым быстрым?

1) При параллельной реализации на аппаратном уровне должно ли оно иметь достаточно низкую задержку, требуя при этом как можно меньше вентилей?Да -> используйте битонический сортировщик или пакетную сортировку нечетным-четным слиянием, задержка равна $ \ Theta (\ log (n) ^ 2) $, а количество компараторов и мультиплексоров равно $ \ Theta (n \ cdot \ log (n) ^ 2) $.

2) Сколько различных значений может иметь каждый элемент?Банкам с каждым возможным значением присвоено уникальное место в памяти или кэше Да -> используйте сортировку по количеству или сортировку по основанию, они обычно имеют линейное время выполнения $ \ Theta (n \ cdot k) $ (сортировка по количеству) или $ \ Theta (n \ cdot m) $ (сортировка по корзинам), но замедляются для большого количества различных значений, так как $ k = 2 ^ {\# число \_ из \_ возможных\_ значений} $ и $ m = \# максимальная \_ длина \_of \_keys $.

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

4) Должна ли сортировка быть стабильной?Да -> использовать сортировку слиянием, либо на месте, либо нет, фиксированного размера или адаптивную, в зависимости от базовой структуры данных и ожидаемого типа данных, даже в тех случаях, когда быстрая сортировка в противном случае была бы предпочтительнее, поскольку стабилизация произвольного алгоритма сортировки требует $ \ Theta (n) $ дополнительной памяти в худшем случае, состоящей из исходных индексов, которые также необходимо синхронизировать с каждой заменой, которая должна выполняться над входными данными, так что каждый выигрыш в производительности, который быстрая сортировка может иметь по сравнению с сортировкой слиянием, вероятно, будет сведен на нет.

5) Может ли размер базовых данных быть привязан к малому или среднему размеру?например ,Является n < 10 000 ...100 000 000 (в зависимости от базовой архитектуры и структуры данных)?Да -> использовать битоническую сортировку или пакетную сортировку нечетно-четным слиянием.Переход 1)

6) Можете ли вы выделить еще $\ Theta (n)$ память?Да -> a) Состоят ли входные данные из больших фрагментов уже отсортированных последовательных данных?-> использовать адаптивную (или естественную) сортировку слиянием или временную сортировку Да -> б) Состоят ли входные данные в основном из элементов, которые находятся почти в нужном месте?-> используйте сортировку пузырьками или сортировку вставкой.Если вы опасаетесь их временной сложности $ \ Theta (n ^ 2) $ (что является патологическим для почти отсортированных данных), возможно, рассмотрите возможность переключения на shell sort с (почти) асимптотически оптимальной последовательностью пробелов, известны некоторые последовательности, которые дают $ \ Theta (n \ cdot \ log (n) ^ 2) $ время выполнения в наихудшем случае, или, возможно, попробуйте comb sort.Я не уверен, что сортировка по оболочке или по гребню будет достаточно эффективной на практике.

Нет -> 7) Можете ли вы выделить еще $\ Theta (\log (n))$ памяти?Да -> a) Допускает ли неизменяемая структура данных направленный последовательный доступ или лучше?Да -> Разрешает ли это только одну последовательность обращений на чтение / запись за раз до тех пор, пока не будет достигнут конец данных (напримернаправленный доступ к ленте)?Да -> я) использую сортировку слиянием, но нет очевидного способа реализовать этот случай на месте, поэтому может потребоваться дополнительная память $ \ Theta (n) $.Но если у вас есть время и яйца, чтобы сделать это, есть способ объединить 2 массива за $ \ Theta (n) $ время, используя только $ \ Theta (\ log (n)) $ пространство стабильным способом, согласно Дональду Э.Кнут "Искусство компьютерного программирования", том 3:Сортировка и поиск", упражнение 5.5.3.утверждает , что существует алгоритм от L.Трабб-Пардо, который так и делает.Однако я сомневаюсь, что это будет быстрее, чем версия naive mergesort или quicksort из приведенного выше примера.Нет, он допускает несколько одновременных обращений к последовательности данных (например,не является ленточным накопителем) -> ii) используйте быструю сортировку, для практических целей я бы рекомендовал либо рандомизированную, либо приближенную медианную.Если вы опасаетесь патологических случаев $ \ Theta (n ^ 2) $, рассмотрите возможность использования intro sort.Если вы одержимы детерминированным поведением, рассмотрите возможность использования алгоритма медианы медианы для выбора элемента pivot, для этого требуется $ \ Theta (n) $ время, а для его наивной реализации требуется $ \ Theta (n) $ пространство (распараллеливаемое), тогда как для его реализации может потребоваться только $ \ Theta (\log (n)) $ пространство (не распараллеливаемое).Однако алгоритм медианы медианы дает вам детерминированную быструю сортировку, которая имеет наихудшее время выполнения $ \ Theta(n \ cdot \ log (n)) $.Нет -> вы облажались (извините, нам нужен хотя бы 1 способ доступа к каждому элементу данных один раз)

Нет -> 8) Можете ли вы выделить небольшой постоянный объем памяти?Да -> Допускает ли базовая структура данных произвольный доступ?Да -> используйте heapsort, он имеет асимптотически оптимальное время выполнения $ \ Theta (n \ cdot \ log (n)) $, но плохую когерентность кэша и плохо распараллеливается.Нет -> ты облажался Нет -> ты облажался

Советы по реализации быстрой сортировки:

1) Наивная двоичная быстрая сортировка требует $ \ Theta (n) $ дополнительной памяти, однако относительно легко уменьшить ее до $ \ Theta (\log (n)) $, переписав последний вызов рекурсии в цикл.Выполнение того же самого для k-арной быстрой сортировки для k> 2 требует $ \ Theta (n ^ { \ log_k (k-1)}) $ space (согласно основной теореме), поэтому двоичная быстрая сортировка требует наименьшего объема памяти, но я был бы рад услышать, знает ли кто-нибудь, может ли k-арная быстрая сортировка для k> 2 быть быстрее, чем двоичная быстрая сортировка в некоторых реальных настройках.

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

Советы по реализации сортировки слиянием:

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

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

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

4) алгоритм слияния можно легко распараллелить, разделив входные данные на k частей приблизительно одинакового размера.Для этого потребуется k ссылок на данные, и хорошо выбрать k таким образом, чтобы все k (или c * k для небольшой константы c>= 1) помещались в ближайшую иерархию памяти (обычно кэш данных L1).Выбор наименьшего из k элементов наивным способом (линейный поиск) занимает $ \ Theta (k) $ времени, тогда как создание минимальной кучи внутри этих k элементов и выбор наименьшего из них требует только амортизированного $ \ Theta (\ log (k)) $ времени (выбор минимального значения, конечно, $ \ Theta (1) $, но нам нужно выполнить небольшое обслуживание, поскольку один элемент удаляется и заменяется другим на каждом шаге).Для распараллеленного слияния всегда требуется $ \ Theta (n) $ памяти, независимо от k.

Из того, что я написал, ясно, что быстрая сортировка часто не является самым быстрым алгоритмом, за исключением случаев, когда применяются все следующие условия:

1) существует более "нескольких" возможных значений

2) базовая структура данных не связана

3) нам не нужен стабильный заказ

4) объем данных достаточно велик, чтобы возникло небольшое неоптимальное асимптотическое время выполнения битонического сортировщика или пакетной нечетно-четной сортировки слиянием

5) данные почти не отсортированы и не состоят из более крупных уже отсортированных частей

6) мы можем получить доступ к последовательности данных одновременно из нескольких мест

7) { операции записи в память особенно дороги (потому что это основной недостаток сортировки слиянием), поскольку это замедляет работу алгоритма сверх возможного неоптимального разделения быстрой сортировки.} или { у нас может быть только $ \ Theta (\log (n)) $ дополнительная память, $ \ Theta (n) $ слишком много (напримервнешнее хранилище) }

p.s.:Кто-нибудь должен помочь мне с форматированием текста.

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

QuickSort, с другой стороны пытается обмениваться номерами, которые находятся в первой части памяти и являются большими, с числами, которые находятся во второй части массива и небольшие (если вы сортируете $ a le B $, Аргумент одинаков в другом смысле), поэтому они быстро распределяются вблизи своего конечного пункта назначения.

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