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

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

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

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

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

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

История

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

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

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

Алгоритм

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

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

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

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

Схема разбиения Ломуто

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

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

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

Схема раздела Хоара

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

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

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

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

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

Весь массив сортируется с помощью quicksort(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) , поскольку левая половина рекурсии включает возвращаемый индекс, функция разбиения должна исключить «хвост» в непродвигающихся сценариях. То есть вместо i должен быть возвращен индекс j («прежний» индекс при пересечении индексов). Следуя аналогичной логике, при рассмотрении примера уже отсортированного массива [0, 1] выбор опорного элемента должен быть «полом», чтобы гарантировать, что указатели остановятся на «первом», а не на «последнем» (при использовании «потолка» в качестве опорного элемента индекс 1 будет возвращен и включен в (lo..p), что приведет к бесконечной рекурсии). Это та же самая причина, по которой следует избегать выбора последнего элемента в качестве опорного элемента.

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

Проблемы внедрения

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

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

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

середина := ⌊(низкая + высокая) / 2⌋ если A[средняя] < A[низкая] поменять местами A[lo] и A[mid]если А[привет] < А[ло] поменять местами A[lo] и A[hi]если A[средний] < A[высокий] поменять местами 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]

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

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

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

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

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

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

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

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

Оптимизации

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

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

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

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

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

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

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

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

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

Если это происходит многократно в каждом разделе, то каждый рекурсивный вызов обрабатывает список размером на единицу меньше предыдущего списка. Следовательно, мы можем сделать 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 элементов с равной вероятностью . В качестве альтернативы, если алгоритм выбирает опорную точку равномерно случайным образом из входного массива, тот же анализ может быть использован для ограничения ожидаемого времени выполнения для любой входной последовательности; затем ожидание берется по случайным выборам, сделанным алгоритмом (Cormen et al. , Introduction to Algorithms , ^[13] Section 7.3).

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

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

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

Когда входные данные представляют собой случайную перестановку, опорный элемент имеет случайный ранг, и поэтому он не гарантированно будет находиться в средних 50 процентах. Однако, когда мы начинаем со случайной перестановки, в каждом рекурсивном вызове опорный элемент имеет случайный ранг в своем списке, и поэтому он находится в средних 50 процентах примерно в половине случаев. Этого достаточно. Представьте, что монета подбрасывается: орел означает, что ранг опорного элемента находится в средних 50 процентах, решка означает, что это не так. Теперь представьте, что монета подбрасывается снова и снова, пока не выпадет k орлов. Хотя это может занять много времени, в среднем требуется всего 2 k подбрасываний, и вероятность того, что монета не выпадет k орлов после 100 k подбрасываний, крайне мала (это можно сделать строгим с помощью границ Чернова ). По тому же аргументу рекурсия быстрой сортировки в среднем завершится при глубине вызова всего . Но если его средняя глубина вызова составляет 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 ) . ^{[17] [20]}

Быстрая сортировка с разбиением на месте и нестабильным разбиением использует только постоянное дополнительное пространство перед выполнением любого рекурсивного вызова. Быстрая сортировка должна хранить постоянное количество информации для каждого вложенного рекурсивного вызова. Поскольку в лучшем случае выполняется не более 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 ) , но среднее время выполнения пирамидальной сортировки обычно считается более медленным, чем быстрая сортировка на месте, в первую очередь из-за худшей локальности ссылок . ^[27] Этот результат спорный; некоторые публикации указывают на обратное. ^{[28] [29]} Главным недостатком быстрой сортировки является сложность реализации, необходимая для избежания плохого выбора опорных точек, и результирующая производительность O ( n ² ) . Introsort — это вариант быстрой сортировки, который решает эту проблему путем переключения на пирамидальную сортировку при обнаружении плохого случая. Основные языки программирования, такие как C++ (в реализациях GNU и LLVM), используют introsort. ^[30]

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

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

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

Выборочный поворот

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

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

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

Варианты

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

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

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

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

Быстрая сортировка по трем основаниям

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

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

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

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

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

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

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

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

Обобщение

Ричард Коул и Дэвид К. Кандатил в 2004 году открыли однопараметрическое семейство алгоритмов сортировки, называемых сортировками разделов, которые в среднем (при равновероятном упорядочении всех входных данных) выполняют большинство сравнений (близких к нижней границе теории информации) и операций; в худшем случае они выполняют сравнения (и также операции); они находятся на месте, требуя только дополнительного пространства. Практическая эффективность и меньшая дисперсия производительности были продемонстрированы в сравнении с оптимизированными быстрыми сортировками (Седжвика и Бентли - Макилроя ) . ^[42] ${\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). Руководство по разработке алгоритмов. Springer. стр. 129. ISBN 978-1-84800-069-8.
4. CL Foster, Алгоритмы, абстракция и реализация , 1992, ISBN 0122626605 , стр. 98 
5. Шустек, Л. (2009). «Интервью: интервью с К. А. Р. Хоаром». Comm. ACM . 52 (3): 38–41. doi :10.1145/1467247.1467261. S2CID  1868477.
6. «Мое интервью Quickshort с сэром Тони Хоаром, изобретателем быстрой сортировки». Марсело М. Де Баррос. 15 марта 2015 г.
7. Бентли, Джон Л.; Макилрой, М. Дуглас (1993). «Разработка функции сортировки». Программное обеспечение: практика и опыт . 23 (11): 1249–1265. CiteSeerX 10.1.1.14.8162 . doi :10.1002/spe.4380231105. S2CID  8822797. 
8. Van Emden, MH (1 ноября 1970 г.). «Алгоритмы 402: Повышение эффективности быстрой сортировки». Commun. ACM . 13 (11): 693–694. doi : 10.1145/362790.362803 . ISSN  0001-0782. S2CID  4774719.
9. Бентли, Джон (2007). «Самый красивый код, который я никогда не писал». В Орам, Энди; Уилсон, Грег (ред.). Красивый код: ведущие программисты объясняют, как они думают . O'Reilly Media. стр. 30. ISBN 978-0-596-51004-6.
10. "Quicksort Partitioning: Hoare vs. Lomuto". cs.stackexchange.com . Получено 3 августа 2015 г. .
11. Макилрой, MD (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). Programming Pearls . Addison-Wesley Professional.
13. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. «Быстрая сортировка». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 170–190. ISBN 0-262-03384-4.
14. Уайлд, Себастьян (2012). Быстрая сортировка Dual Pivot в Java 7 (Диссертация). Технический университет Кайзерслаутерна.
15. Hoare, CAR (1 января 1962 г.). «Быстрая сортировка». The Computer Journal . 5 (1): 10–16. doi : 10.1093/comjnl/5.1.10 . ISSN  0010-4620.
16. Чандрамули, Бадриш; Голдштейн, Джонатан (18 июня 2014 г.). «Терпение — добродетель». Труды Международной конференции ACM SIGMOD 2014 г. по управлению данными . Sigmod '14. Snowbird Utah USA: ACM. стр. 731–742. doi :10.1145/2588555.2593662. ISBN 978-1-4503-2376-5. S2CID  7830071.
17. Sedgewick, Robert (1 сентября 1998 г.). Алгоритмы на языке C: основы, структуры данных, сортировка, поиск, части 1–4 (3-е изд.). Pearson Education. ISBN 978-81-317-1291-7.
18. qsort.c в GNU libc : [1], [2]
19. http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html ^{[ постоянная мертвая ссылка ]}
20. Седжвик, Р. (1978). «Реализация программ быстрой сортировки». Comm. ACM . 21 (10): 847–857. doi :10.1145/359619.359631. S2CID  10020756.
21. LaMarca, Anthony; Ladner, Richard E. (1999). "Влияние кэшей на производительность сортировки". Journal of Algorithms . 31 (1): 66–104. CiteSeerX 10.1.1.27.1788 . doi :10.1006/jagm.1998.0985. S2CID  206567217. Хотя сохранение небольших подмассивов до конца имеет смысл с точки зрения количества инструкций, это совершенно неправильно с точки зрения производительности кэша. 
22. Умут А. Акар, Гай Э. Блеллох, Маргарет Рид-Миллер и Канат Тангвонгсан, Быстрая сортировка и нижние границы сортировки, Параллельные и последовательные структуры данных и алгоритмы . 2013.
23. Брешеарс, Клэй (2012). «Быстрая сортировка разделов с помощью префиксного сканирования». Доктор Доббс .
24. Миллер, Расс; Боксер, Лоренс (2000). Алгоритмы последовательные и параллельные: единый подход. Prentice Hall. ISBN 978-0-13-086373-7.
25. Powers, David MW (1991). Распараллеленная быстрая сортировка и радиксортировка с оптимальным ускорением . Труды Международной конференции по технологиям параллельных вычислений. CiteSeerX 10.1.1.57.9071 . 
26. Другой может либо иметь 1 элемент, либо быть пустым (иметь 0 элементов), в зависимости от того, включен ли опорный элемент в один из подразделов, как в процедуре разбиения Хоара, или исключен из обоих, как в процедуре Ломуто.
27. Эделькамп, Стефан; Вайс, Армин (7–8 января 2019 г.). Эффективная сортировка в худшем случае с помощью QuickMergesort . ALENEX 2019: 21-й семинар по разработке алгоритмов и экспериментам. Сан-Диего. arXiv : 1811.99833 . doi : 10.1137/1.9781611975499.1. ISBN 978-1-61197-549-9На небольших экземплярах пирамидальная сортировка уже значительно медленнее быстрой сортировки (в наших экспериментах более чем на 30% для n = 2 ¹⁰ ), а на более крупных экземплярах она страдает от плохого поведения кэша (в наших экспериментах более чем в восемь раз медленнее быстрой сортировки при сортировке 2 ²⁸ элементов).
28. Хсие, Пол (2004). «Повторный взгляд на сортировку». azillionmonkeys.com.
29. MacKay, David (декабрь 2005 г.). "Пирамидальная сортировка, быстрая сортировка и энтропия". Архивировано из оригинала 1 апреля 2009 г.
30. Кутенин, Данила (20 апреля 2022 г.). «Изменение std::sort в масштабе Google и далее». Экспериментальный чиллаунж .
31. Wild, Sebastian; Nebel, Markus E. (2012). Анализ среднего случая двойной быстрой сортировки Java 7. Европейский симпозиум по алгоритмам. arXiv : 1310.7409 . Bibcode : 2013arXiv1310.7409W.
32. Ярославский, Владимир (2009). "Dual-Pivot Quicksort" (PDF) . Архивировано из оригинала (PDF) 2 октября 2015 г.
33. Wild, S.; Nebel, M.; Reitzig, R.; Laube, U. (7 января 2013 г.). Разработка быстрой сортировки Dual Pivot в Java 7 с использованием MaLiJAn . Труды. Общество промышленной и прикладной математики. стр. 55–69. doi :10.1137/1.9781611972931.5. ISBN 978-1-61197-253-5.
34. "Массивы". Java Platform SE 7. Oracle . Получено 4 сентября 2014 г.
35. Уайлд, Себастьян (3 ноября 2015 г.). «Почему быстрая сортировка с двойным опорным алгоритмом быстрая?». arXiv : 1511.01138 [cs.DS].
36. Кушагра, Шрину; Лопес-Ортис, Алехандро; Цяо, Аурик; Манро, Дж. Ян (2014). Многоточечная быстрая сортировка: теория и эксперименты . Труды Практикума по разработке алгоритмов и экспериментам (ALENEX). doi : 10.1137/1.9781611973198.6 .
37. Кушагра, Шрину; Лопес-Ортис, Алехандро; Манро, Дж. Ян; Цяо, Аурик (7 февраля 2014 г.). Multi-Pivot Quicksort: Theory and Experiments (PDF) (презентация семинара). Ватерлоо, Онтарио .
38. Моцкин, Д.; Хансен, КЛ (1982), «Эффективная внешняя сортировка с минимальными требованиями к пространству», Международный журнал компьютерных и информационных наук , 11 (6): 381–396, doi :10.1007/BF00996816, S2CID  6829805
39. Дэвид М. В. Пауэрс, Параллельная унификация: практическая сложность, Австралазийский семинар по компьютерной архитектуре, Университет Флиндерса, январь 1995 г.
40. Калигоси, Канела; Сандерс, Питер (11–13 сентября 2006 г.). Как неверные предсказания ветвей влияют на быструю сортировку (PDF) . ESA 2006: 14-й ежегодный европейский симпозиум по алгоритмам. Цюрих . doi :10.1007/11841036_69.
41. Эделькамп, Стефан; Вайс, Армин (22 апреля 2016 г.). «BlockQuicksort: как неправильные прогнозы ветвей не влияют на быструю сортировку». arXiv : 1604.06697 [cs.DS].
42. Ричард Коул, Дэвид К. Кандатил: «Анализ среднего случая сортировок разбиения», Европейский симпозиум по алгоритмам, 14–17 сентября 2004 г., Берген, Норвегия. Опубликовано: Lecture Notes in Computer Science 3221, Springer Verlag, стр. 240–251.

Ссылки

• Седжвик, Р. (1978). «Реализация программ быстрой сортировки». Comm. ACM . 21 (10): 847–857. doi :10.1145/359619.359631. S2CID  10020756.
• Дин, BC (2006). "Простой анализ ожидаемого времени выполнения для рандомизированных алгоритмов "разделяй и властвуй"". Дискретная прикладная математика . 154 : 1–5. doi : 10.1016/j.dam.2005.07.005 .
• Hoare, CAR (1961). "Алгоритм 63: Разделение". Comm. ACM . 4 (7): 321. doi :10.1145/366622.366642. S2CID  52800011.
• Hoare, CAR (1961). «Алгоритм 65: Найти». Comm. ACM . 4 (7): 321–322. doi :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: Сортировка и поиск , третье издание. Addison-Wesley, 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). «Оптимальные стратегии выборки в быстрой сортировке и быстром выборе». SIAM J. Comput. 31 (3): 683–705. CiteSeerX  10.1.1.17.4954 . doi :10.1137/S0097539700382108.
• Бентли, Дж. Л.; Макилрой, М. Д. (1993). «Разработка функции сортировки». Программное обеспечение: практика и опыт . 23 (11): 1249–1265. CiteSeerX  10.1.1.14.8162 . doi :10.1002/spe.4380231105. S2CID  8822797.

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

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