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

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

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

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

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

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

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

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

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

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

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

Среднее Дело не существует!

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

Почему примечание?$O$

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

Есть два выхода:

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

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

   • Быстрая сортировка: 11,667$11.667(n+1)\ln(n)-1.74n-18.74$
   • Слияние:$12.5 n \ln(n)$
   • Heapsort: $16 n \ln(n) +0.01n$
   • Сортировка вставок: ^{[ источник ]}$2.25n^2+7.75n-3ln(n)$
     

   Эти результаты показывают, что быстрая сортировка является самой быстрой. Но это доказано только на искусственной машине Кнута, это не обязательно подразумевает что-то, скажем, ваш x86 ПК. Также обратите внимание, что алгоритмы по-разному относятся к небольшим входам:
   
   ^{[ источник ]}

2. Проанализируйте абстрактные основные операции .

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

   • Быстрая сортировка: сравнений и перестановок в среднем$2n\ln(n)$$\frac13n\ln(n)$
   • Mergesort: сравнений, но до обращений к массиву (mergesort не основан на swap, поэтому мы не можем это посчитать).$1.44n\ln(n)$$8.66n\ln(n)$
   • вставки: сравнения и в среднем.$\frac14n^2$$\frac14n^2$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В одном из учебников по программированию в моем университете мы попросили студентов сравнить производительность быстрой сортировки, сортировки слиянием, сортировки вставкой и встроенной в Python list.sort (называемой Timsort ). Результаты эксперимента меня сильно удивили, поскольку встроенная сортировка list.sort работала намного лучше, чем другие алгоритмы сортировки, даже в случаях, когда легко выполнялась быстрая сортировка, сбой слияния. Поэтому преждевременно делать вывод, что обычная реализация быстрой сортировки является лучшей на практике. Но я уверен, что есть гораздо лучшая реализация быстрой сортировки или какая-то гибридная версия.

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

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

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

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

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

$\cal{O}(n \log n)$

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

$k \approx 10$

$O(n \lg n)$

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

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

• Сравнение быстрой сортировки с другими алгоритмами сортировки

• Сравнение сортировки кучи с другими алгоритмами сортировки

$\Theta(n^2)$$\Theta(n\log n)$

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

ОБНОВЛЕНИЕ:: (после комментариев Яномы и Свика)

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

Рассмотрим следующую последовательность:

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

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

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

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

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

Редактировать: языки программирования, такие как Java, Python и Perl, также используют сортировку слиянием или, точнее, производную, такую ​​как сортировка слиянием или сортировка слиянием для больших наборов и сортировка вставкой для небольших наборов. (Java также использует быструю сортировку с двойным поворотом, которая быстрее, чем простая быстрая сортировка.)

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

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

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

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

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

$\Theta(\log(n)^2)$$\Theta(n \cdot \log(n)^2)$

$\Theta(n \cdot k)$$\Theta(n \cdot m)$$k=2^{\#number\_of\_Possible\_values}$$m = \#maximum\_length\_of\_keys$

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

$\Theta(n)$

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

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

$\Theta(\log(n))$$\Theta(n)$$\Theta(n)$$\Theta(\log(n))$$\Theta(n^2)$$\Theta(n)$$\Theta(n)$$\Theta(\log(n))$$\Theta(n \cdot \log(n))$

$\Theta(n \cdot \log(n))$

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

$\Theta(n)$$\Theta(\log(n))$$\Theta(n^{\log_k(k-1)})$

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

Реализация советов по слиянию:

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

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

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

$\Theta(k)$$\Theta(\log(k))$$\Theta(1)$$\Theta(n)$

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

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

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

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

4) данные достаточно велики, чтобы небольшое субоптимальное асимптотическое время работы битонного сортировщика или нечетно-четного слияния Бэтчера

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

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

$\Theta(\log(n))$$\Theta(n)$

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

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

$a \le b$