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

Алгоритм сортировки «разделяй и властвуй»

Быстрая сортировка — это эффективный алгоритм сортировки общего назначения . Быстрая сортировка была разработана британским учёным-компьютерщиком Тони Хоаром в 1959 году ^[1] и опубликована в 1961 году. ^[2] Это до сих пор широко используемый алгоритм сортировки. В целом, это немного быстрее, чем сортировка слиянием и пирамидальная сортировка для рандомизированных данных, особенно в больших распределениях. ^[3]

Быстрая сортировка — это алгоритм «разделяй и властвуй» . Он работает путем выбора «поворотного» элемента из массива и разделения других элементов на два подмассива в зависимости от того, меньше они или больше, чем опорный элемент. По этой причине ее иногда называют сортировкой по обмену разделами . ^[4] Затем подмассивы сортируются рекурсивно . Это можно сделать на месте , требуя небольшого дополнительного объема памяти для выполнения сортировки.

Быстрая сортировка — это сортировка сравнения , что означает, что она может сортировать элементы любого типа, для которых определено отношение «меньше» (формально, общий порядок ). Это сортировка на основе сравнения, поскольку элементы a и b меняются местами только в том случае, если их относительный порядок был получен при транзитивном замыкании предыдущих результатов сравнения. Большинство реализаций быстрой сортировки нестабильны , а это означает, что относительный порядок одинаковых элементов сортировки не сохраняется.

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

История

Алгоритм быстрой сортировки был разработан в 1959 году Тони Хоаром, когда он был приглашенным студентом Московского государственного университета . В то время Хоар работал над проектом машинного перевода для Национальной физической лаборатории . В процессе перевода ему нужно было отсортировать слова в русских предложениях, прежде чем искать их в русско-английском словаре, который был записан на магнитной ленте в алфавитном порядке . ^[5] Поняв, что его первая идея — сортировка вставками — будет медленной, он придумал новую идею. Он написал часть раздела в Mercury Autocode , но у него возникли проблемы со списком несортированных сегментов. По возвращении в Англию его попросили написать код для Shellsort . Хоар упомянул своему боссу, что знает более быстрый алгоритм, и тот поспорил на шесть пенсов , что он этого не знает. Его босс в конце концов признал, что он проиграл пари. Хоар опубликовал статью о своем алгоритме в The Computer Journal Volume 5, Issue 1, 1962, страницы 10–16. Позже Хоар узнал об АЛГОЛе и его способности выполнять рекурсию, что позволило ему опубликовать улучшенную версию алгоритма АЛГОЛа в журнале « Communications of the Association for Computing Machinery» , ведущем журнале по компьютерным наукам того времени. ^{[2] [6]} Код ALGOL опубликован в Communications of the ACM (CACM), том 4, выпуск 7 июля 1961 г., стр. 321. Алгоритм 63: разделение и Алгоритм 64: Быстрая сортировка.

Быстрая сортировка получила широкое распространение, появившись, например, в Unix как подпрограмма сортировки библиотеки по умолчанию. Следовательно, оно дало свое имя подпрограмме стандартной библиотеки C qsort ^[7] и эталонной реализации Java .

Кандидатская диссертация Роберта Седжвика в 1975 году считается важной вехой в изучении быстрой сортировки, где он решил множество открытых проблем, связанных с анализом различных схем выбора основных элементов, включая сортировку выборки , адаптивное разделение Ван Эмдена ^[8] , а также получение ожидаемого числа. сравнений и обменов. ^[7] Джон Бентли и Дуг Макилрой в 1993 году включили различные улучшения для использования в библиотеках программирования, включая метод работы с равными элементами и схему поворота, известную как псевдомедиана из девяти, где выборка из девяти элементов делится на группы по три и затем выбирается медиана из трех медиан из трех групп. ^[7] Бентли описал другую, более простую и компактную схему разбиения в своей книге « Жемчужины программирования» , которую он приписал Нико Ломуто. Позже Бентли написал, что он использовал версию Хоара в течение многих лет, но так и не понял ее, но версия Ломуто была достаточно простой, чтобы оказаться верной. ^[9] В том же эссе Бентли описал Quicksort как «самый красивый код, который я когда-либо писал». Схема разбиения Ломуто также была популяризирована учебником « Введение в алгоритмы», хотя она уступает схеме Хоара, поскольку в среднем делает в три раза больше перестановок и снижается до времени выполнения O ( n ² ) , когда все элементы равны. ^{[10] [ собственный источник? В 1998 году Макилрой} разработал функцию AntiQuicksort ( aqsort ), которая постоянно приводит даже его вариант быстрой сортировки 1993 года к квадратичному поведению, создавая состязательные данные на лету. ^[11]

Алгоритм

Полный пример быстрой сортировки случайного набора чисел. Заштрихованный элемент — это ось. Он всегда выбирается в качестве последнего элемента раздела. Однако такой выбор всегда последнего элемента в разделе в качестве опорного приводит к низкой производительности ( O ( n ² ) ) на уже отсортированных массивах или массивах идентичных элементов. Поскольку подмассивы отсортированных/идентичных элементов часто возникают ближе к концу процедуры сортировки на большом наборе, версии алгоритма быстрой сортировки, в которых центральный элемент выбран в качестве среднего элемента, работают гораздо быстрее, чем алгоритм, описанный на этой диаграмме на большие наборы чисел.

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

1. Если в диапазоне меньше двух элементов, вернитесь немедленно, поскольку делать нечего. Возможно, для других очень коротких длин применяется специальный метод сортировки, а оставшаяся часть этих шагов пропускается.
2. В противном случае выберите значение, называемое опорной точкой , которое встречается в диапазоне (точный способ выбора зависит от процедуры разделения и может включать случайность).
3. Разделите диапазон: измените порядок его элементов, определяя при этом точку разделения, так, чтобы все элементы со значениями меньшими, чем ось, стояли перед делением, а все элементы со значениями, большими, чем ось, шли после него; элементы, равные опорной точке, могут идти в любом направлении. Поскольку присутствует по крайней мере один экземпляр опорной точки, большинство процедур разделения гарантируют, что значение, которое оказывается в точке деления, равно опорной точке и теперь находится в своем конечном положении (но завершение быстрой сортировки от этого не зависит, до тех пор, пока производятся поддиапазоны строго меньшие, чем исходные).
4. Рекурсивно применить быструю сортировку к поддиапазону до точки деления и к поддиапазону после нее, по возможности исключая из обоих диапазонов элемент, равный опорной точке в точке деления. (Если разделение создает возможно больший поддиапазон вблизи границы, где известно, что все элементы равны опорной точке, их также можно исключить.)

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

Схема раздела Ломуто

Эта схема приписывается Нико Ломуто и популяризируется Бентли в его книге « Жемчужины программирования» ^[12] и Корменом и др. в своей книге «Введение в алгоритмы» . ^[13] В большинстве формулировок эта схема выбирает в качестве опорного последний элемент массива. Алгоритм поддерживает индекс i, поскольку он сканирует массив, используя другой индекс j , так что элементы от lo до i-1 (включительно) меньше опорного элемента, а элементы от i до j (включительно) равны или больше, чем вращаться. Поскольку эта схема более компактна и проста для понимания, она часто используется во вводных материалах, хотя она менее эффективна, чем исходная схема Хоара, например, когда все элементы равны. ^[14] Сложность быстрой сортировки по этой схеме снижается до O ( n ² ) , когда массив уже в порядке, поскольку раздел является наихудшим из возможных. ^[10] Были предложены различные варианты повышения производительности, включая различные способы выбора опорной точки, работы с равными элементами, использования других алгоритмов сортировки, таких как сортировка вставками для небольших массивов и так далее. В псевдокоде быстрая сортировка, которая сортирует элементы массива A от lo до hi (включительно) , может быть выражена как: ^[13]

// Сортирует массив (часть массива), делит его на разделы, затем сортирует их. Алгоритм быстрой сортировки (A, lo, hi) is  // Убедитесь, что индексы находятся в правильном порядке,  если lo >= hi || lo < 0 тогда  возвращаться  // Разделяем массив и получаем сводный индекс p := раздел (A, вот, привет)  // Сортировка двух разделов Quicksort(A, lo, p - 1) // Левая сторона сводной таблицы Quicksort(A, p + 1, hi) // Правая сторона сводной таблицы// Делит массив на две части. Алгоритм partion(A, lo, hi) является поворотным := A[hi] // Выбираем последний элемент в качестве опорного. // Временный сводный индекс я := ло - 1 for j := lo to hi - 1 do  // Если текущий элемент меньше или равен опорному элементу  if A[j] <= опорный элемент , то  // Перемещаем временный опорный индекс вперед я := я + 1 // Меняем местами текущий элемент на элемент во временном сводном индексе, меняем A[i] на A[j] // Перемещаем элемент поворота в правильное положение поворота (между меньшим и большим элементами) я := я + 1 поменять местами A[i] на A[hi] return i // индекс поворота

Сортировка всего массива осуществляется с помощью быстрой сортировки(A, 0, length(A) - 1) .

Схема перегородок Хоара

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

Исходная схема секционирования, описанная Тони Хоаром , использует два указателя (индекса диапазона), которые начинаются с обоих концов разделяемого массива, затем движутся навстречу друг другу, пока не обнаружат инверсию: пара элементов, один из которых больше границы. (Термины Хоара для значения поворота) в первом указателе и на единицу меньше границы во втором указателе; если в этот момент первый указатель все еще находится перед вторым, эти элементы находятся в неправильном порядке относительно друг друга, и затем они меняются местами. ^[15] После этого указатели перемещаются внутрь, и поиск инверсии повторяется; когда в конечном итоге указатели пересекаются (первые точки следуют за вторыми), обмен не производится; найден действительный раздел с точкой разделения между скрещенными указателями (любые записи, которые могут находиться строго между скрещенными указателями, равны опорной точке и могут быть исключены из обоих сформированных поддиапазонов). При такой формулировке возможно, что один поддиапазон окажется всем исходным диапазоном, что помешает алгоритму развиваться. Поэтому Хоар предусматривает, что в конце поддиапазон, содержащий опорный элемент (который все еще находится в исходном положении), может быть уменьшен в размере путем исключения этого опорного элемента после (при необходимости) замены его на элемент поддиапазона, ближайший к разделение; таким образом обеспечивается завершение быстрой сортировки.

Что касается этого исходного описания, реализации часто вносят незначительные, но важные изменения. Примечательно, что схема, представленная ниже, включает элементы, равные стержню среди кандидатов на инверсию (поэтому критерии «больше или равно» и «меньше или равно» используются вместо «больше» и «меньше» соответственно; поскольку в формулировке используется do ... while, а не повтор ... до тех пор , пока это фактически не отражается использованием строгих операторов сравнения ^{[ необходимы пояснения ]} ). Хотя нет причин обменивать элементы, равные границе, это изменение позволяет опустить проверки самих указателей, которые в противном случае необходимы для обеспечения того, чтобы они не вышли за пределы диапазона. Действительно, поскольку в диапазоне присутствует по крайней мере один экземпляр опорного значения, первое перемещение любого указателя не может пройти через этот экземпляр, если используется инклюзивный тест; как только обмен выполнен, оба обмениваемых элемента теперь находятся строго впереди указателя, который их нашел, что предотвращает смещение этого указателя. (Последнее верно независимо от используемого теста, поэтому можно будет использовать инклюзивный тест только при поиске первой инверсии. Однако использование инклюзивного теста повсюду также гарантирует, что деление около середины будет найдено, когда все элементы в диапазоны равны, что дает важный выигрыш в эффективности сортировки массивов со многими одинаковыми элементами.) Риска непродвижения разделения можно избежать способом, отличным от описанного Хоаром. Такое разделение может произойти только в том случае, если не обнаружено никаких инверсий, когда оба указателя перемещаются к опорному элементу на первой итерации (тогда они считаются пересекшимися, и обмена не происходит). Возвращаемое деление находится после конечной позиции второго указателя, поэтому следует избегать случая, когда точка поворота является последним элементом диапазона, а все остальные меньше его. Следовательно, при выборе точки поворота следует избегать последнего элемента (в описании Хоара это может быть любой элемент в диапазоне); здесь это делается путем округления средней позиции с помощью функции. ^[16] Это показывает, что аргументы в пользу правильности реализации схемы разделения Хоара могут быть тонкими, и в них легко ошибиться.floor

В псевдокоде ^[13 ]

// Сортирует массив (часть массива), делит его на разделы, затем сортирует их. Алгоритм быстрой сортировки(A, lo, hi) is  if lo >= 0 && hi >= 0 && lo < hi then p := раздел (A, вот, привет) Quicksort(A, lo, p) // Примечание: теперь включена опорная точка быстрая сортировка (A, p + 1, привет)// Делит массив на два раздела . Алгоритм раздела (A, lo, hi) равен  // Значение опорного элемента. Pivot := A[lo] // Выбираем первый элемент в качестве опорного. // Левый индекс я := ло - 1 // Правый индекс j := привет + 1 цикл навсегда  // Переместите левый индекс вправо хотя бы один раз, и пока элемент в  // левом индексе меньше, чем опорный элемент,  do i := i + 1 while A[i] < Pivot  // Переместите правый индекс влево хотя бы один раз, и пока элемент с  // правым индексом больше, чем опорный элемент,  do j := j - 1 while A[j] > Pivot // Если индексы пересеклись, возвращаем  if i >= j , затем  возвращаем j  // Меняем местами элементы с левым и правым индексами,  меняем A[i] на A[j]

Весь массив сортируется быстрой сортировкой(A, 0, length(A) - 1) .

Схема Хоара более эффективна, чем схема разбиения Ломуто, поскольку в среднем она выполняет в три раза меньше операций подкачки. Кроме того, как уже упоминалось, данная реализация создает сбалансированный раздел, даже если все значения равны. ^{[10] [ собственный источник? ]} , чего нет в схеме Ломуто. Как и схема секционирования Ломуто, секционирование Хоара также привело бы к ухудшению качества быстрой сортировки до O ( n ² ) для уже отсортированных входных данных, если опорный элемент был выбран в качестве первого или последнего элемента. Однако при использовании среднего элемента в качестве опорного элемента результаты сортировки данных практически без свопов в разделах одинакового размера, что приводит к наилучшему поведению быстрой сортировки, т. е. O ( n log( n ) ) . Как и другие, разделение Хоара не обеспечивает стабильной сортировки. В этой схеме окончательное местоположение опорной точки не обязательно совпадает с возвращаемым индексом, поскольку опорная точка и элементы, равные опорной точке, могут оказаться в любом месте внутри раздела после шага разделения и не могут быть отсортированы до тех пор, пока не будет выполнен базовый случай раздел с одним элементом достигается с помощью рекурсии. Следовательно, следующие два сегмента, на которых повторяется основной алгоритм, — это (lo..p) (элементы ≤ поворот) и (p+1..hi) (элементы ≥ поворот), в отличие от (lo..p-1) и (p+1..hi) как в схеме Ломуто.

Последующие рекурсии (расширение предыдущего абзаца)

Давайте немного остановимся на следующих двух сегментах, на которых повторяется основной алгоритм. Поскольку мы используем строгие компараторы (>, <) в циклах «do... while» , чтобы не допустить выхода за пределы диапазона, существует вероятность того, что сама точка поворота будет заменена другими элементами в функции секционирования. Таким образом, индекс, возвращаемый функцией секционирования, не обязательно находится там, где находится фактическая опорная точка. Рассмотрим пример [5, 2, 3, 1, 0] , следуя схеме: после первого раздела массив становится [0, 2, 1, 3, 5] , возвращаемый «индекс» равен 2, что является номер 1, когда настоящая опорная точка, с которой мы решили начать разбиение, была номером 3. На этом примере мы видим, как необходимо включать возвращаемый индекс функции секционирования в наши последующие рекурсии. В результате нам предоставляется выбор: либо рекурсия по (lo..p) и (p+1..hi) , либо (lo..p - 1) и (p..hi) . Какой из двух вариантов мы выберем, зависит от того, какой индекс ( i или j ) мы возвращаем в функции статистического распределения, когда индексы пересекаются, и от того, как мы выбираем опорную точку в функции статистического распределения ( пол или потолок ).

Давайте сначала рассмотрим выбор рекурсии (lo..p) и (p+1..hi) на примере сортировки массива, в котором существует несколько одинаковых элементов [0, 0] . Если индекс i («последний» индекс) возвращается после пересечения индексов в функции секционирования, индекс 1 будет возвращен после первого секционирования. Последующая рекурсия по (lo..p) будет по (0, 1), что соответствует точно такому же массиву [0, 0] . Производится непродвигающееся разделение, вызывающее бесконечную рекурсию. Поэтому очевидно, что при рекурсии по (lo..p) и (p+1..hi) , поскольку левая половина рекурсии включает возвращаемый индекс, задача функции секционирования заключается в исключении «хвоста» в не -продвижение сценариев. То есть индекс j («бывший» индекс при пересечении индексов) должен быть возвращен вместо i. Следуя аналогичной логике, при рассмотрении примера уже отсортированного массива [0, 1] выбор точки поворота должен быть «полом», чтобы гарантировать, что указатели останавливаются на «первом», а не на «последнем» (с «потолок» в качестве опорной точки, индекс 1 будет возвращен и включен в (lo..p) , что приведет к бесконечной рекурсии). По той же причине следует избегать выбора последнего элемента в качестве опорного.

Выбор рекурсии для (lo..p - 1) и (p..hi) следует той же логике, что и выше. Поскольку правая половина рекурсии включает возвращаемый индекс, задача функции секционирования заключается в исключении «головы» в непродвигающихся сценариях. Индекс i («последний» индекс после пересечения индексов) в статистической сумме необходимо вернуть, а «потолок» необходимо выбрать в качестве опорной точки. Два нюанса снова становятся очевидными при рассмотрении примеров сортировки массива, в котором существует несколько одинаковых элементов ( [0, 0] ), и уже отсортированного массива [0, 1] соответственно. Примечательно, что при использовании версии рекурсии по той же причине следует избегать выбора первого элемента в качестве опорного.

Проблемы реализации

Выбор точки поворота

В самых ранних версиях быстрой сортировки в качестве опорного элемента часто выбирался самый левый элемент раздела. К сожалению, это приводит к наихудшему поведению уже отсортированных массивов, что является довольно распространенным вариантом использования. ^[17] Проблема была легко решена путем выбора либо случайного индекса для опорной точки, либо среднего индекса раздела, либо (особенно для более длинных разделов) выбора медианы первого , среднего и последнего элемента раздела для опорной точки ( согласно рекомендациям Седжвика ). ^[18] Это правило «медианы из трех» учитывает случай сортировки (или обратной сортировки) входных данных и дает лучшую оценку оптимального опорного элемента (истинной медианы), чем выбор любого отдельного элемента, когда нет информации о порядок ввода известен.

Фрагмент кода медианы из трех для раздела Lomuto:

Mid := ⌊(lo + hi) / 2⌋, если A[mid] < A[lo] поменять местами A[lo] на A[mid]если A[hi] < A[lo] поменять местами A[lo] на A[hi]если A[mid] < A[hi] поменять местами A[mid] на A[hi]стержень := A[привет]

Сначала он помещает медиану A[hi], затем это новое значение A[hi]используется в качестве опорной точки, как в базовом алгоритме, представленном выше.

В частности, ожидаемое количество сравнений, необходимое для сортировки n элементов (см. § Анализ рандомизированной быстрой сортировки) со случайным выбором сводного элемента, составляет 1,386 n log n . Поворот медианы из трех снижает это значение до C _{n , 2} ≈ 1,188 n log n , за счет трехпроцентного увеличения ожидаемого количества свопов. ^[7] Еще более строгое правило поворота для больших массивов — выбрать девятый , рекурсивную медиану трех (Mo3), определяемую как ^[7]

девятый( a ) = медиана(Mo3(первый1/3a ) , Mo3(средний1/3a ) , Mo3(конечный1/3а ) )

Выбор опорного элемента также осложняется наличием целочисленного переполнения . Если граничные индексы сортируемого подмассива достаточно велики, наивное выражение для среднего индекса ( lo + hi )/2 вызовет переполнение и предоставит недопустимый сводный индекс. Этого можно избежать, используя, например, lo + ( hi − lo )/2 для индексации среднего элемента за счет более сложной арифметики. Аналогичные проблемы возникают и при некоторых других методах выбора поворотного элемента.

Повторяющиеся элементы

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

Чтобы решить проблему схемы разделения Ломуто (иногда называемую проблемой голландского национального флага ^[7] ), можно использовать альтернативную процедуру разделения с линейным временем, которая разделяет значения на три группы: значения, меньшие, чем ось, значения, равные стержню, и значения больше, чем ось. (Бентли и Макилрой называют это «толстым разделом», и он уже был реализован в qsort версии 7 Unix . ^[7] ). Значения, равные опорной точке, уже отсортированы, поэтому необходимы только разделы «меньше» и «больше». рекурсивно сортироваться. В псевдокоде алгоритм быстрой сортировки выглядит следующим образом:

// Сортирует массив (часть массива), делит его на разделы, а затем сортирует их. Алгоритм быстрой сортировки(A, lo, hi) следующий:  if lo >= 0 && lo < hi then lt, gt := part(A, lo, привет) // Несколько возвращаемых значений быстрая сортировка (A, lo, lt - 1) быстрая сортировка (A, GT + 1, привет)// Делит массив на три части . Алгоритм раздела (A, lo, hi) равен  // Значение опорного центра : = A[(lo + hi) / 2] // Выбираем средний элемент в качестве опорного (целочисленное деление)  // Меньший, равный и больший индекс lt := вот экв := вот гт := привет  // Итерируем и сравниваем все элементы с опорным элементом  while eq <= gt do  if A[eq] < Pivot then  // Меняем местами элементы с равными и меньшими индексами,  меняем местами A[eq] на A[lt] // Увеличиваем меньший индекс л := л + 1 // Увеличиваем равный индекс экв := экв + 1 else  if A[eq] > Pivot then  // Поменяйте местами элементы с равным и большим индексом,  поменяйте местами A[eq] на A[gt] // Уменьшите больший индекс гт := гт - 1 else  // если A[eq] = опорная точка , то  // Увеличить равный индекс экв := экв + 1  // Возвращаем меньший и больший индексы  return lt, gt

Алгоритм partitionвозвращает индексы к первому («самому левому») и последнему («крайнему правому») элементу среднего раздела. Любой другой элемент раздела равен опорному элементу и поэтому сортируется. Следовательно, элементы раздела не обязательно включать в рекурсивные вызовы quicksort.

Наилучший случай для алгоритма теперь возникает, когда все элементы равны (или выбираются из небольшого набора из k ≪ n элементов). В случае, если все элементы равны, модифицированная быстрая сортировка выполнит только два рекурсивных вызова для пустых подмассивов и, таким образом, завершится за линейное время (при условии, что подпрограмма partitionзанимает не более линейного времени).

Оптимизации

Другие важные оптимизации, также предложенные Седжвиком и широко используемые на практике: ^{[19] [20]}

• Чтобы убедиться, что используется не более O (log n ) пространства, сначала повторите меньшую сторону раздела, затем используйте хвостовой вызов , чтобы вернуться к другой, или обновите параметры, чтобы они больше не включали теперь отсортированную меньшую сторону, и повторите, чтобы отсортировать большую сторону.
• Когда количество элементов ниже некоторого порога (например, десяти элементов), переключитесь на нерекурсивный алгоритм сортировки, такой как сортировка вставками , который выполняет меньше замен, сравнений или других операций с такими небольшими массивами. Идеальный «порог» будет варьироваться в зависимости от деталей конкретной реализации.
• Более старый вариант предыдущей оптимизации: когда количество элементов меньше порога k , просто останавливаемся; затем, после обработки всего массива, выполните для него сортировку вставкой. Досрочная остановка рекурсии оставляет массив k -отсортированным, что означает, что каждый элемент находится не более чем на k позициях от своей окончательной отсортированной позиции. В этом случае для завершения сортировки вставкой требуется время O ( kn ) , которое является линейным, если k является константой. ^{[21] [12] : 117} По сравнению с оптимизацией «много мелких сортировок», эта версия может выполнять меньше инструкций, но она неоптимально использует кэш-память в современных компьютерах. ^[22]

Распараллеливание

Формулировка быстрой сортировки «разделяй и властвуй» делает ее поддающейся распараллеливанию с использованием параллелизма задач . Этап секционирования выполняется за счет использования параллельного алгоритма суммирования префиксов для вычисления индекса для каждого элемента массива в его секции секционированного массива. ^{[23] [24]} Учитывая массив размером n , шаг разделения выполняет работу O( n ) за время O (log n ) и требует O( n ) дополнительного рабочего пространства. После разделения массива два раздела можно рекурсивно сортировать параллельно. Предполагая идеальный выбор опорных точек, параллельная быстрая сортировка сортирует массив размера n за время O( n log n ) за время O(log ² n ) , используя дополнительное пространство O( n ) .

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

Другие, более сложные алгоритмы параллельной сортировки могут обеспечить еще лучшие временные рамки. ^[25] Например, в 1991 году Дэвид Пауэрс описал параллельную быструю сортировку (и связанную с ней поразрядную сортировку ), которая может работать за время O (log n ) в CRCW (параллельное чтение и параллельная запись) PRAM (параллельная машина с произвольным доступом) с n процессоров путем неявного разделения. ^[26]

Формальный анализ

Анализ наихудшего случая

Самый несбалансированный раздел возникает, когда один из подсписков, возвращаемых процедурой разделения, имеет размер n - 1 . ^[27] Это может произойти, если опорный элемент оказывается наименьшим или наибольшим элементом в списке, или в некоторых реализациях (например, схема разделения Lomuto, как описано выше), когда все элементы равны.

Если это происходит неоднократно в каждом разделе, то каждый рекурсивный вызов обрабатывает список размером на один меньше, чем предыдущий список. Следовательно, мы можем сделать n - 1 вложенных вызовов, прежде чем достигнем списка размером 1. Это означает, что дерево вызовов представляет собой линейную цепочку из n - 1 вложенных вызовов. При i- м вызове для разделения требуется O ( n − i ) и , поэтому в этом случае быстрая сортировка занимает O ( n ² ) времени. ${\displaystyle \textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})}$

Анализ наилучшего случая

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

Анализ среднего случая

Чтобы отсортировать массив из n различных элементов, быстрая сортировка занимает время ожидания O ( n log n ) , усредненное по всем n ! перестановки n элементов с равной вероятностью . В качестве альтернативы, если алгоритм равномерно случайным образом выбирает опорную точку из входного массива, тот же анализ можно использовать для ограничения ожидаемого времени выполнения для любой входной последовательности; затем ожидание принимается за случайный выбор, сделанный алгоритмом (Кормен и др. , Введение в алгоритмы , ^[13] , раздел 7.3).

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

Использование процентилей

Если каждый центральный элемент имеет рейтинг где-то посередине 50 процентов, то есть между 25-м и 75-м процентилем, то он разделяет элементы как минимум с 25% и максимум с 75% с каждой стороны. Если бы мы могли последовательно выбирать такие опорные точки, нам нужно было бы разбивать список только в большинстве случаев, прежде чем мы достигнем списков размера 1, что дало бы алгоритм O ( n log n ) . ${\displaystyle \log _{4/3}n}$

Когда входные данные представляют собой случайную перестановку, ведущая точка имеет случайный ранг, поэтому не гарантируется, что она будет находиться в середине 50 процентов. Однако когда мы начинаем со случайной перестановки, при каждом рекурсивном вызове ведущая точка имеет случайный ранг в своем списке, и поэтому примерно в половине случаев она находится в середине 50 процентов. Это достаточно хорошо. Представьте себе, что подбрасывается монета: орел означает, что ранг опорной точки находится в середине 50 процентов, решка означает, что это не так. Теперь представьте, что монету подбрасывают снова и снова, пока на ней не выпадет k орлов. Хотя это может занять много времени, в среднем требуется всего 2 тыс. подбрасываний, и вероятность того, что на монете не выпадет k орлов после 100 тыс . подбрасываний, крайне мала (это можно сделать строгим, используя границы Чернова ). По тому же аргументу рекурсия Quicksort завершится в среднем при глубине вызова всего . Но если его средняя глубина вызовов равна O (log n ) , и каждый уровень дерева вызовов обрабатывает не более n элементов, общий объем выполненной работы в среднем равен продукту O ( n log n ) . Алгоритму не нужно проверять, что точка поворота находится в средней половине — если мы попадаем в нее какую-то постоянную долю раз, этого достаточно для желаемой сложности. ${\displaystyle 2\log _{4/3}n}$

Использование повторений

Альтернативный подход — установить рекуррентное соотношение для фактора T ( n ) , времени, необходимого для сортировки списка размера n . В наиболее несбалансированном случае один вызов быстрой сортировки требует работы O ( n ) плюс два рекурсивных вызова для списков размера 0 и n −1 , поэтому рекуррентное соотношение имеет вид

${\displaystyle T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}$

Это то же соотношение, что и для ^{сортировки} вставкой и сортировки выбором , и оно решается в худшем случае T ( n ) = O ( n2 ) .

В наиболее сбалансированном случае один вызов быстрой сортировки включает в себя работу O ( n ) плюс два рекурсивных вызова для списков размера n /2 , поэтому рекуррентное соотношение имеет вид

${\displaystyle T(n)=O(n)+2T\left({\frac {n}{2}}\right).}$

Основная теорема для повторений по принципу «разделяй и властвуй» говорит нам, что T ( n ) = O ( n log n ) .

Ниже приводится схема формального доказательства ожидаемой временной сложности O ( n log n ) . Предположим, что дубликатов нет, поскольку дубликаты можно обрабатывать с помощью предварительной и постобработки с линейным временем, или рассматривать случаи проще, чем анализируемые. Когда входные данные представляют собой случайную перестановку, ранг опорной точки является равномерным случайным от 0 до n - 1 . Тогда результирующие части разбиения имеют размеры i и n − i −1 , а i является равномерно случайным от 0 до n −1 . Итак, усредняя по всем возможным разбиениям и отмечая, что количество сравнений для раздела равно n - 1 , среднее количество сравнений по всем перестановкам входной последовательности можно точно оценить, решив рекуррентное соотношение:

${\displaystyle C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)}$

${\displaystyle nC(n)=(n+1)C(n-1)+2n-2}$

${\displaystyle {\begin{aligned}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n+1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}}\\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{\frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n+1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\sum _{i=2}^{n}{\frac {2}{i+1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{x}}\mathrm {d} x=2\ln n\end{aligned}}}$

Решение рекуррентного уравнения дает C ( n ) знак равно 2 n ln n ≈ 1,39 n log ₂ n .

Это означает, что в среднем быстрая сортировка работает примерно на 39% хуже, чем в лучшем случае. В этом смысле он ближе к лучшему, чем к худшему. Сортировка сравнением не может использовать в среднем меньше, чем log ₂ ( n !) сравнений для сортировки n элементов (как описано в статье «Сортировка сравнения ») , а в случае больших n аппроксимация Стирлинга дает log ₂ ( n !) ≈ n (log ₂ n − log ₂ e ) , поэтому быстрая сортировка не намного хуже идеальной сортировки сравнением. Такое быстрое среднее время выполнения является еще одной причиной практического превосходства быстрой сортировки над другими алгоритмами сортировки.

Использование двоичного дерева поиска

Следующее двоичное дерево поиска (BST) соответствует каждому выполнению быстрой сортировки: начальный опорный узел является корневым узлом; ось левой половины — это корень левого поддерева, ось правой половины — это корень правого поддерева и так далее. Количество сравнений при выполнении быстрой сортировки равно количеству сравнений при построении BST последовательностью вставок. Таким образом, среднее количество сравнений для рандомизированной быстрой сортировки равно средней стоимости построения BST, когда вставленные значения образуют случайную перестановку. ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$

Рассмотрим BST, созданный путем вставки последовательности значений, образующей случайную перестановку. Обозначим через C стоимость создания BST. У нас есть , где — двоичная случайная величина, показывающая, проводилось ли во время вставки сравнение с . ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle C=\sum _{i}\sum _{j<i}c_{i,j}}$ ${\displaystyle c_{i,j}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

В силу линейности ожидания ожидаемое значение C равно . ${\displaystyle \operatorname {E} [C]}$ ${\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})}$

Исправьте i и j < i . Значения после сортировки определяют интервал j +1 . Основное структурное наблюдение заключается в том, что оно сравнивается с в алгоритме тогда и только тогда, когда оно попадает в один из двух интервалов, соседних с . ${\displaystyle {x_{1},x_{2},\ldots ,x_{j}}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

Обратите внимание, что поскольку это случайная перестановка, она также является случайной перестановкой, поэтому вероятность, которая является соседней с, равна точно . ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle (x_{1},x_{2},\ldots ,x_{j},x_{i})}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle {\frac {2}{j+1}}}$

Закончим кратким расчетом:

${\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).}$

Пространственная сложность

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

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

• Используется локальное секционирование. Этот нестабильный раздел требует O (1) пространства.
• После разделения сначала (рекурсивно) сортируется раздел с наименьшим количеством элементов, требующий не более O (log n ) пространства. Затем другой раздел сортируется с использованием хвостовой рекурсии или итерации, которая не добавляется в стек вызовов. Эта идея, как обсуждалось выше, была описана Р. Седжвиком и сохраняет глубину стека ограниченной O (log n ) . ^{[18] [21]}

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

С точки зрения некоторой сложности, такие переменные, как lo и hi, не используют постоянное пространство; для индексации списка из n элементов требуется O (log n ) бит . Поскольку такие переменные есть в каждом кадре стека, быстрая сортировка с использованием трюка Седжвика требует O ((log n ) ² ) бит пространства. Однако это требование к пространству не так уж и страшно, поскольку, если бы список содержал отдельные элементы, ему потребовалось бы как минимум O ( n log n ) бит пространства.

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

Связь с другими алгоритмами

Быстрая сортировка — это оптимизированная по пространству версия сортировки двоичного дерева . Вместо последовательной вставки элементов в явное дерево быстрая сортировка организует их одновременно в дерево, которое подразумевается рекурсивными вызовами. Алгоритмы выполняют точно такие же сравнения, но в другом порядке. Часто желательным свойством алгоритма сортировки является стабильность – то есть порядок элементов, которые сравниваются равными, не изменяется, что позволяет естественным образом контролировать порядок многоключевых таблиц (например, списков каталогов или папок). Это свойство сложно поддерживать для быстрой сортировки на месте (которая использует только постоянное дополнительное пространство для указателей и буферов и дополнительное пространство O (log n ) для управления явной или неявной рекурсией). Для вариантов быстрой сортировки, требующих дополнительной памяти из-за представлений с использованием указателей (например, списков или деревьев) или файлов (фактически списков), поддерживать стабильность тривиально. Более сложные или привязанные к диску структуры данных имеют тенденцию увеличивать временные затраты, как правило, увеличивая использование виртуальной памяти или диска.

Самым прямым конкурентом быстрой сортировки является пирамидальная сортировка . Преимущество пирамидальной сортировки заключается в простоте и времени выполнения в худшем случае O ( n log n ) , но среднее время работы пирамидальной сортировки обычно считается медленнее, чем быстрая сортировка на месте, в первую очередь из-за худшей локальности ссылки . ^[28] Этот результат является спорным; некоторые публикации указывают на обратное. ^{[29] [30]} Основным недостатком быстрой сортировки является сложность реализации, необходимая для того, чтобы избежать неправильного выбора опорной точки и, как следствие, производительности O ( n ² ) . Интросорт — это вариант быстрой сортировки, который решает эту проблему путем переключения на пирамидальную сортировку при обнаружении плохого случая. Основные языки программирования, такие как C++ (в реализациях GNU и LLVM), используют интросортировку. ^[31]

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

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

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

Поворот на основе выбора

Алгоритм выбора выбирает k- е наименьшее число из списка; в целом это более простая задача, чем сортировка. Один простой, но эффективный алгоритм выбора работает почти так же, как быстрая сортировка, и поэтому известен как быстрый выбор . Разница в том, что вместо рекурсивных вызовов обоих подсписков он выполняет только один хвостовой рекурсивный вызов для подсписка, содержащего нужный элемент. Это изменение снижает среднюю сложность до линейного времени или ^{времени} O ( n ) , что оптимально для выбора, но в худшем случае алгоритм выбора по-прежнему равен O ( n2 ) .

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

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

Варианты

Многоповоротная быстрая сортировка

Вместо разделения на два подмассива с использованием одной опорной точки, быстрая сортировка с несколькими опорными точками (также мультибыстрая сортировка ^[22] ) разбивает входные данные на некоторое количество подмассивов с использованием s - 1 опорных точек. Хотя случай с двумя поворотами ( s = 3 ) рассматривался Седжвиком и другими еще в середине 1970-х годов, полученные алгоритмы на практике были не быстрее, чем «классическая» быстрая сортировка. ^[32] Проведенная в 1999 году оценка мультибыстрой сортировки с переменным количеством операций, настроенной на эффективное использование кэша процессора, показала, что она увеличивает количество команд примерно на 20%, но результаты моделирования показали, что она будет более эффективной на очень больших объемах операций. входы. ^[22] Версия быстрой сортировки с двумя точками, разработанная Ярославским в 2009 году ^[33], оказалась достаточно быстрой ^[34] для реализации в Java 7 , поскольку стандартный алгоритм сортировки массивов примитивов (сортировка массивов объектов выполняется с помощью Тимсорта ). ^[35] Впоследствии было обнаружено, что преимущество в производительности этого алгоритма в основном связано с производительностью кэша, ^[36] и экспериментальные результаты показывают, что вариант с тремя точками может работать даже лучше на современных машинах. ^{[37] [38]}

Внешняя быстрая сортировка

Для дисковых файлов возможна внешняя сортировка на основе разделения, аналогичная быстрой сортировке. Это медленнее, чем внешняя сортировка слиянием, но не требует дополнительного дискового пространства. Используются 4 буфера, 2 на ввод, 2 на вывод. Пусть N = количество записей в файле, B = количество записей в буфере и M = N/B = количество сегментов буфера в файле. Данные читаются (и записываются) с обоих концов файла внутрь. Пусть X представляет сегменты, которые начинаются в начале файла, а Y представляют сегменты, которые начинаются в конце файла. Данные считываются в буферы чтения X и Y. Выбирается сводная запись, и записи в буферах X и Y, кроме сводной записи, копируются в буфер записи X в возрастающем порядке и в буфер записи Y в порядке убывания на основе сравнения со сводной записью. Как только буфер X или Y заполнен, он записывается в файл, а следующий буфер X или Y считывается из файла. Процесс продолжается до тех пор, пока все сегменты не будут прочитаны и не останется один буфер записи. Если этот буфер является буфером записи X, к нему добавляется сводная запись и записывается буфер X. Если этот буфер является буфером записи Y, сводная запись добавляется к буферу Y и записывается в буфер Y. Это составляет один шаг разделения файла, и теперь файл состоит из двух подфайлов. Начальная и конечная позиции каждого подфайла помещаются/извлекаются в автономный стек или основной стек посредством рекурсии. Чтобы ограничить пространство стека до O(log2(n)), сначала обрабатывается меньший подфайл. Для автономного стека поместите в стек параметры большего подфайла и выполните итерацию по меньшему подфайлу. Для рекурсии сначала выполните рекурсию по меньшему подфайлу, а затем выполните итерацию для обработки большего подфайла. Если количество записей в подфайле меньше или равно 4 B, он сортируется на месте с помощью быстрой сортировки и записывается. Теперь этот подфайл отсортирован и находится на своем месте в файле. Процесс продолжается до тех пор, пока все подфайлы не будут отсортированы и не будут на своих местах. Среднее количество проходов по файлу составляет примерно 1 + ln(N+1)/(4 B), но шаблон в худшем случае — N проходов (что эквивалентно O(n^2) для внутренней сортировки в худшем случае). ^[39]

Трехсторонняя поразрядная быстрая сортировка

Этот алгоритм представляет собой комбинацию поразрядной сортировки и быстрой сортировки. Выберите элемент из массива (центральную точку) и рассмотрите первый символ (ключ) строки (многоклавишный). Разделите оставшиеся элементы на три набора: те, чей соответствующий символ меньше, равен или больше символа опорной точки. Рекурсивно сортируйте разделы «меньше» и «больше» по одному и тому же символу. Рекурсивно сортируйте раздел «равно» по следующему символу (ключу). Учитывая, что мы сортируем с использованием байтов или слов длиной W бит, лучшим случаем является O ( KN ) , а худшим случаем O (2 ^K N ) или по крайней мере O ( N ² ) , как для стандартной быстрой сортировки, заданной для уникальных ключей N <2. ^K и K — это скрытая константа во всех стандартных алгоритмах сортировки сравнением , включая быструю сортировку. Это своего рода трехсторонняя быстрая сортировка, в которой средний раздел представляет собой (тривиально) отсортированный подмассив элементов, которые точно равны опорному.

Быстрая поразрядная сортировка

Также разработан Пауэрсом как параллельный алгоритм PRAM O ( K ) . Это снова комбинация поразрядной сортировки и быстрой сортировки, но решение о разделении влево/вправо при быстрой сортировке принимается для последовательных битов ключа и, таким образом, равно O ( KN ) для N K -битных ключей. Все алгоритмы сортировки сравнением неявно предполагают трансдихотомическую модель с K в Θ (log N ) , так как если K меньше, мы можем сортировать за время O ( N ) , используя хеш-таблицу или целочисленную сортировку . Если K ≫ log N , но элементы уникальны в пределах O (log N ) бит, оставшиеся биты не будут проверяться ни быстрой сортировкой, ни быстрой поразрядной сортировкой. В противном случае все алгоритмы сортировки сравнения также будут иметь одинаковые накладные расходы на просмотр O ( K ) относительно бесполезных битов, но быстрая поразрядная сортировка позволит избежать наихудшего поведения O ( N ² ) стандартной быстрой сортировки и быстрой поразрядной сортировки и будет даже быстрее. в лучшем случае этих алгоритмов сравнения при этих условиях uniqueprefix( K ) ≫ log N . См. Пауэрс ^[40] для дальнейшего обсуждения скрытых издержек при сравнении, поразрядной и параллельной сортировке.

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

В любом алгоритме сортировки, основанном на сравнении, минимизация количества сравнений требует максимизации объема информации, получаемой от каждого сравнения, а это означает, что результаты сравнения непредсказуемы. Это приводит к частым неправильным предсказаниям ветвей , ограничивая производительность. ^[41] BlockQuicksort ^[42] перестраивает вычисления быстрой сортировки для преобразования непредсказуемых ветвей в зависимости данных . При секционировании входные данные разбиваются на блоки среднего размера (которые легко помещаются в кэш данных ), а два массива заполняются позициями элементов для замены. (Чтобы избежать условных ветвей, позиция безоговорочно сохраняется в конце массива, а индекс конца увеличивается, если требуется замена.) Второй проход заменяет элементы в позициях, указанных в массивах. Оба цикла имеют только один условный переход — тест на завершение, который обычно и выполняется.

Метод BlockQuicksort включен в реализацию STL C++ компании LLVM , libcxx, что обеспечивает улучшение на 50 % при обработке случайных целочисленных последовательностей. Быстрая сортировка с обходом шаблонов ( pdqsort ), версия интросортировки, также включает этот метод. ^[31]

Частичная и инкрементная быстрая сортировка

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

Обобщение

Ричард Коул и Дэвид К. Кандатил в 2004 году открыли семейство однопараметрических алгоритмов сортировки, называемых сортировками разделов, которые в среднем (при равновероятном порядке всех входных данных) выполняют большинство сравнений (близко к нижней границе теории информации) и операции; в худшем случае они выполняют сравнения (а также операции); они находятся на месте и требуют только дополнительного места. Практическая эффективность и меньшая разница в производительности были продемонстрированы при использовании оптимизированных быстрых сортировок ( Sedgewick и Bentley - McIlroy ). ^[43] ${\displaystyle n\log n+{O}(n)}$ ${\displaystyle {\Theta }(n\log n)}$ ${\displaystyle {\Theta }(n\log ^{2}n)}$ ${\displaystyle {O}(\log n)}$

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

• Портал компьютерного программирования

• Introsort  — гибридный алгоритм сортировки

Примечания

1. "Сэр Энтони Хоар". Музей истории компьютеров. Архивировано из оригинала 3 апреля 2015 года . Проверено 22 апреля 2015 г.
2. Хоар, ЦАР (1961). «Алгоритм 64: Быстрая сортировка». Комм. АКМ . 4 (7): 321. дои : 10.1145/366622.366644.
3. Скиена, Стивен С. (2008). Руководство по проектированию алгоритмов. Спрингер. п. 129. ИСБН 978-1-84800-069-8.
4. К. Л. Фостер, Алгоритмы, абстракция и реализация , 1992, ISBN 0122626605 , стр. 98 
5. Шустек, Л. (2009). «Интервью: Интервью с CAR Hoare». Комм. АКМ . 52 (3): 38–41. дои : 10.1145/1467247.1467261. S2CID  1868477.
6. "Мое короткое интервью с сэром Тони Хоаром, изобретателем быстрой сортировки" . Марсело М Де Баррос. 15 марта 2015 г.
7. Бентли, Джон Л.; Макилрой, М. Дуглас (1993). «Разработка функции сортировки». Программное обеспечение: практика и опыт . 23 (11): 1249–1265. CiteSeerX 10.1.1.14.8162 . дои : 10.1002/спе.4380231105. S2CID  8822797. 
8. Ван Эмден, Миннесота (1 ноября 1970 г.). «Алгоритмы 402: повышение эффективности быстрой сортировки». Коммун. АКМ . 13 (11): 693–694. дои : 10.1145/362790.362803 . ISSN  0001-0782. S2CID  4774719.
9. Бентли, Джон (2007). «Самый красивый код, который я никогда не писал». В Ораме, Энди; Уилсон, Грег (ред.). Красивый код: ведущие программисты объясняют, как они думают . О'Рейли Медиа. п. 30. ISBN 978-0-596-51004-6.
10. «Разделение быстрой сортировки: Хоар против Ломуто». cs.stackexchange.com . Проверено 3 августа 2015 г.
11. Макилрой, доктор медицины (10 апреля 1999 г.). «Смертельный противник быстрой сортировки» (PDF) . Программное обеспечение: практика и опыт . 29 (4): 341–344. doi :10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R. S2CID  35935409.
12. Джон Бентли (1999). Жемчуг программирования . Аддисон-Уэсли Профессионал.
13. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. «Быстрая сортировка». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 170–190. ISBN 0-262-03384-4.
14. Уайлд, Себастьян (2012). Быстрая сортировка Dual Pivot в Java 7 (Диссертация). Технический университет Кайзерслаутерна.
15. Хоар, ЦАР (1 января 1962 г.). «Быстрая сортировка». Компьютерный журнал . 5 (1): 10–16. дои : 10.1093/comjnl/5.1.10 . ISSN  0010-4620.
16. во многих языках это стандартное поведение целочисленного деления.
17. Чандрамули, Бадриш; Гольдштейн, Джонатан (18 июня 2014 г.). «Терпение – добродетель». Материалы Международной конференции ACM SIGMOD 2014 по управлению данными . Сигмод '14. Сноуберд, Юта, США: ACM. стр. 731–742. дои : 10.1145/2588555.2593662. ISBN 978-1-4503-2376-5. S2CID  7830071.
18. Седжвик, Роберт (1 сентября 1998 г.). Алгоритмы на C: основы, структуры данных, сортировка, поиск, части 1–4 (3-е изд.). Пирсон Образование. ISBN 978-81-317-1291-7.
19. qsort.c в GNU libc : [1], [2]
20. http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html ^{[ постоянная мертвая ссылка ]}
21. Седжвик, Р. (1978). «Реализация программ быстрой сортировки». Комм. АКМ . 21 (10): 847–857. дои : 10.1145/359619.359631. S2CID  10020756.
22. Ламарка, Энтони; Ладнер, Ричард Э. (1999). «Влияние кешей на производительность сортировки». Журнал алгоритмов . 31 (1): 66–104. CiteSeerX 10.1.1.27.1788 . дои : 10.1006/jagm.1998.0985. S2CID  206567217. Хотя сохранение небольших подмассивов до конца имеет смысл с точки зрения количества инструкций, это совершенно неправильно с точки зрения производительности кэша. 
23. Умут А. Акар, Гай Э. Блеллок, Маргарет Рид-Миллер и Канат Тангвонгсан, Быстрая сортировка и сортировка нижних границ, параллельные и последовательные структуры данных и алгоритмы . 2013.
24. Бреширс, Клэй (2012). «Быстрая сортировка раздела посредством сканирования префиксов». Доктор Добб .
25. Миллер, Расс; Боксер, Лоуренс (2000). Алгоритмы последовательные и параллельные: единый подход. Прентис Холл. ISBN 978-0-13-086373-7.
26. Пауэрс, Дэвид М.В. (1991). Параллелизованные быстрая сортировка и поразрядная сортировка с оптимальным ускорением . Учеб. Международная конференция. по параллельным вычислительным технологиям. CiteSeerX 10.1.1.57.9071 . 
27. Другой может либо иметь 1 элемент, либо быть пустым (иметь 0 элементов), в зависимости от того, включен ли стержень в один из подразделов, как в процедуре разделения Хоара, или исключен из них обоих, как в процедуре Ломуто. .
28. Эделькамп, Стефан; Вайс, Армин (7–8 января 2019 г.). Эффективная сортировка в наихудшем случае с помощью QuickMergesort . ALENEX 2019: 21-й семинар по алгоритмической разработке и экспериментам. Сан Диего. arXiv : 1811.99833 . дои : 10.1137/1.9781611975499.1. ISBN 978-1-61197-549-9. на небольших экземплярах пирамидальная сортировка уже значительно медленнее, чем быстрая сортировка (в наших экспериментах более 30% для n = 2 ¹⁰ ), а на более крупных экземплярах она страдает от плохого поведения кэша (в наших экспериментах более чем в восемь раз медленнее, чем быстрая сортировка для сортировки 2 ^{28 )} . элементы).
29. Се, Пол (2004). «Возвращение к сортировке». azillionmonkeys.com.
30. Маккей, Дэвид (декабрь 2005 г.). «Групповая сортировка, быстрая сортировка и энтропия». Архивировано из оригинала 1 апреля 2009 года.
31. Кутенин, Данила (20 апреля 2022 г.). «Изменение std::sort в масштабе Google и за его пределами». Экспериментальный холод .
32. Уайлд, Себастьян; Небель, Маркус Э. (2012). Анализ среднего случая быстрой сортировки с двойным поворотом в Java 7 . Европейский симпозиум по алгоритмам. arXiv : 1310.7409 . Бибкод : 2013arXiv1310.7409W.
33. Ярославский, Владимир (2009). «Быстрая сортировка с двумя поворотами» (PDF) . Архивировано из оригинала (PDF) 2 октября 2015 года.
34. Уайлд, С.; Небель, М.; Райциг, Р.; Лаубе, У. (7 января 2013 г.). Разработка быстрой сортировки Dual Pivot в Java 7 с использованием MaLiJAn . Слушания. Общество промышленной и прикладной математики. стр. 55–69. дои : 10.1137/1.9781611972931.5. ISBN 978-1-61197-253-5.
35. «Массивы». Платформа Java SE 7 . Оракул . Проверено 4 сентября 2014 г.
36. Уайлд, Себастьян (3 ноября 2015 г.). «Почему быстрая сортировка с двойным поворотом?». arXiv : 1511.01138 [cs.DS].
37. Кушагра, Шрину; Лопес-Ортис, Алехандро; Цяо, Аурик; Манро, Дж. Ян (2014). Многоповоротная быстрая сортировка: теория и эксперименты . Учеб. Семинар по алгоритмической разработке и экспериментам (ALENEX). дои : 10.1137/1.9781611973198.6 .
38. Кушагра, Шрину; Лопес-Ортис, Алехандро; Манро, Дж. Ян; Цяо, Аурик (7 февраля 2014 г.). Multi-Pivot Quicksort: Theory and Experiments (PDF) (презентация семинара). Ватерлоо, Онтарио .
39. Моцкин, Д.; Хансен, CL (1982), «Эффективная внешняя сортировка с минимальными требованиями к пространству», Международный журнал компьютерных и информационных наук , 11 (6): 381–396, doi : 10.1007/BF00996816, S2CID  6829805
40. Дэвид М.В. Пауэрс, Параллельное объединение: практическая сложность, Австралазийский семинар по компьютерной архитектуре, Университет Флиндерса, январь 1995 г.
41. Калигоси, Канела; Сандерс, Питер (11–13 сентября 2006 г.). Как неверные прогнозы ветвей влияют на быструю сортировку (PDF) . ЕКА 2006: 14-й ежегодный европейский симпозиум по алгоритмам. Цюрих . дои : 10.1007/11841036_69.
42. Эделькамп, Стефан; Вайс, Армин (22 апреля 2016 г.). «BlockQuicksort: как неверные прогнозы ветвей не влияют на быструю сортировку». arXiv : 1604.06697 [cs.DS].
43. Ричард Коул, Дэвид К. Кандатил: «Анализ среднего случая сортировки разделов», Европейский симпозиум по алгоритмам, 14–17 сентября 2004 г., Берген, Норвегия. Опубликовано: Конспекты лекций по информатике 3221, Springer Verlag, стр. 240–251.

Рекомендации

• Седжвик, Р. (1978). «Реализация программ быстрой сортировки». Комм. АКМ . 21 (10): 847–857. дои : 10.1145/359619.359631. S2CID  10020756.
• Дин, Британская Колумбия (2006). «Простой анализ ожидаемого времени работы для рандомизированных алгоритмов «разделяй и властвуй». Дискретная прикладная математика . 154 : 1–5. дои : 10.1016/j.dam.2005.07.005 .
• Хоар, ЦАР (1961). «Алгоритм 63: Разделение». Комм. АКМ . 4 (7): 321. дои : 10.1145/366622.366642. S2CID  52800011.
• Хоар, ЦАР (1961). «Алгоритм 65: Найти». Комм. АКМ . 4 (7): 321–322. дои : 10.1145/366622.366647.
• Хоар, ЦАР (1962). «Быстрая сортировка». Вычислить. Дж. 5 (1): 10–16. дои : 10.1093/comjnl/5.1.10 .(Перепечатано в журнале Хоар и Джонс: Очерки информатики, 1989.)
• Массер, Дэвид Р. (1997). «Интроспективные алгоритмы сортировки и выбора». Программное обеспечение: практика и опыт . 27 (8): 983–993. doi :10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
• Дональд Кнут . Искусство компьютерного программирования , Том 3: Сортировка и поиск , Третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89685-0 . Страницы 113–122 раздела 5.2.2: Сортировка по обмену. 
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill , 2001. ISBN 0-262-03293-7 . Глава 7: Быстрая сортировка, стр. 145–164. 
• Фарон Моллер . Анализ быстрой сортировки. CS 332: Разработка алгоритмов. Департамент компьютерных наук Университета Суонси .
• Мартинес, К.; Роура, С. (2001). «Оптимальные стратегии выборки в быстрой сортировке и быстром выборе». СИАМ Дж. Компьютер. 31 (3): 683–705. CiteSeerX  10.1.1.17.4954 . дои : 10.1137/S0097539700382108.
• Бентли, Дж.Л.; Макилрой, доктор медицины (1993). «Разработка функции сортировки». Программное обеспечение: практика и опыт . 23 (11): 1249–1265. CiteSeerX  10.1.1.14.8162 . дои : 10.1002/спе.4380231105. S2CID  8822797.

Внешние ссылки

• «Анимированные алгоритмы сортировки: быстрая сортировка». Архивировано из оригинала 2 марта 2015 года . Проверено 25 ноября 2008 г.– графическая демонстрация
• «Анимированные алгоритмы сортировки: быстрая сортировка (трехстороннее разделение)». Архивировано из оригинала 6 марта 2015 года . Проверено 25 ноября 2008 г.
• Структуры открытых данных – Раздел 11.1.2 – Быстрая сортировка, Пэт Морин
• Интерактивная иллюстрация быстрой сортировки с пошаговым описанием кода
• Быстрая сортировка с помощью Quicksort, глубокого погружения, удобного для новичков.