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

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

Анимированная визуализация алгоритма быстрой сортировки. Горизонтальные линии — это значения поворота.
Сорт	Алгоритм сортировки
Худшая производительность	$O(n^{2})$
Лучшая производительность	$O(n\log n)$ (простой раздел) или $O(n)$ (трехстороннее разделение и равные ключи)
Средняя производительность	$O(n\log n)$
Наихудшая пространственная сложность	$O(n)$ вспомогательный (наивный) $O(\log n)$ вспомогательный (Хоар, 1962)
Оптимальный	Нет

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

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

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

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

История

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

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

Докторская диссертация Роберта Седжвика в 1975 году считается важной вехой в изучении быстрой сортировки, где он решил множество открытых проблем, связанных с анализом различных схем выбора опорных точек, включая Samplesort , адаптивное разделение Ван Эмдена. а также получение ожидаемого количества сравнений и замен. Джон Бентли и Дуг Макилрой в 1993 году включили различные улучшения для использования в библиотеках программирования, включая метод работы с равными элементами и схему поворота, известную как псевдомедиана из девяти, где выборка из девяти элементов делится на группы по три, а затем медиану. выбирается из трех медиан из трех групп. Бентли описал другую, более простую и компактную схему разделения в своей книге «Жемчужины программирования» , которую он приписал Нико Ломуто (бывшему итальянскому певцу 60-х годов). Позже Бентли написал, что он использовал версию Хоара в течение многих лет, но так и не понял ее, но версия Ломуто была достаточно простой, чтобы оказаться верной. В том же эссе Бентли описал Quicksort как «самый красивый код, который я когда-либо писал». Схема разбиения Ломуто также была популяризирована учебником « Введение в алгоритмы» , хотя она уступает схеме Хоара, поскольку в среднем делает в три раза больше перестановок и деградирует до O ( n ² ) время выполнения, когда все элементы равны. Макилрой в дальнейшем разработал AntiQuicksort ( aqsort ) в 1998 году, которая постоянно приводит даже его вариант быстрой сортировки 1993 года к квадратичному поведению, создавая состязательные данные на лету.

Алгоритм

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

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

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

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

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

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

// Sorts a (portion of an) array, divides it into partitions, then sorts thosealgorithm quicksort(A, lo, hi) is   // Ensure indices are in correct order  if lo >= hi || lo < 0 then     return      // Partition array and get the pivot index  p := partition(A, lo, hi)         // Sort the two partitions  quicksort(A, lo, p - 1) // Left side of pivot  quicksort(A, p + 1, hi) // Right side of pivot// Divides array into two partitionsalgorithm partition(A, lo, hi) is   pivot := A[hi] // Choose the last element as the pivot  // Temporary pivot index  i := lo  for j := lo to hi - 1 do     // If the current element is less than or equal to the pivot    if A[j] <= pivot then       // Swap the current element with the element at the temporary pivot index      swap A[i] with A[j]      // Move the temporary pivot index forward      i := i + 1  // Swap the pivot with the last element  swap A[i] with A[hi]  return i // the pivot index

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

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

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

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

Что касается этого исходного описания, реализации часто вносят незначительные, но важные изменения. Примечательно, что схема, представленная ниже, включает элементы, равные стержню среди кандидатов на инверсию (поэтому критерии «больше или равно» и «меньше или равно» используются вместо «больше» и «меньше» соответственно; поскольку в формулировке используется делать ... пока, а не повторять ... до тех пор, пока это не будет фактически отражено использованием операторов строгого сравнения ). Хотя нет причин обменивать элементы, равные опорной точке, это изменение позволяет опустить тесты самих указателей, которые в противном случае необходимы для обеспечения того, чтобы они не вышли за пределы диапазона. Действительно, поскольку в диапазоне присутствует по крайней мере один экземпляр опорного значения, первое перемещение любого указателя не может пройти через этот экземпляр, если используется инклюзивный тест; как только обмен выполнен, оба обмениваемых элемента теперь находятся строго впереди указателя, который их нашел, что предотвращает смещение этого указателя. (Последнее верно независимо от используемого теста, поэтому можно будет использовать инклюзивный тест только при поиске первой инверсии. Однако использование инклюзивного теста повсюду также гарантирует, что деление около середины будет найдено, когда все элементы в диапазоны равны, что дает важный выигрыш в эффективности сортировки массивов со многими одинаковыми элементами.) Риска непродвижения разделения можно избежать способом, отличным от описанного Хоаром. Такое разделение может произойти только в том случае, если не обнаружено никаких инверсий, когда оба указателя перемещаются к опорному элементу на первой итерации (тогда они считаются пересекшимися, и обмена не происходит).

В псевдокоде ​

// Sorts a (portion of an) array, divides it into partitions, then sorts thosealgorithm quicksort(A, lo, hi) is   if lo >= 0 && hi >= 0 && lo < hi then    p := partition(A, lo, hi)     quicksort(A, lo, p) // Note: the pivot is now included    quicksort(A, p + 1, hi) // Divides array into two partitionsalgorithm partition(A, lo, hi) is   // Pivot value  pivot := A[lo] // Choose the first element as the pivot  // Left index  i := lo - 1   // Right index  j := hi + 1  loop forever     // Move the left index to the right at least once and while the element at    // the left index is less than the pivot    do i := i + 1 while A[i] < pivot        // Move the right index to the left at least once and while the element at    // the right index is greater than the pivot    do j := j - 1 while A[j] > pivot    // If the indices crossed, return    if i >= j then return j        // Swap the elements at the left and right indices    swap A[i] with A[j]

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

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

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

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

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

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

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

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

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

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

mid := ⌊(lo + hi) / 2⌋if A[mid] < A[lo]    swap A[lo] with A[mid]if A[hi] < A[lo]    swap A[lo] with A[hi]if A[mid] < A[hi]    swap A[mid] with A[hi]pivot := A[hi]

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

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

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

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

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

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

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

// Sorts a (portion of an) array, divides it into partitions, then sorts thosealgorithm quicksort(A, lo, hi) is  if lo >= 0 && lo < hi then    lt, gt := partition(A, lo, hi) // Multiple return values    quicksort(A, lo, lt - 1)    quicksort(A, gt + 1, hi)// Divides array into three partitionsalgorithm partition(A, lo, hi) is  // Pivot value  pivot := A[(lo + hi) / 2] // Choose the middle element as the pivot (integer division)    // Lesser, equal and greater index  lt := lo  eq := lo  gt := hi    // Iterate and compare all elements with the pivot  while eq <= gt do    if A[eq] < pivot then      // Swap the elements at the equal and lesser indices      swap A[eq] with A[lt]      // Increase lesser index      lt := lt + 1      // Increase equal index      eq := eq + 1    else if A[eq] > pivot then      // Swap the elements at the equal and greater indices      swap A[eq] with A[gt]      // Decrease greater index      gt := gt - 1    else // if A[eq] = pivot then      // Increase equal index      eq := eq + 1    // Return lesser and greater indices  return lt, gt

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

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

Оптимизации

Другими важными оптимизациями, также предложенными Седжвиком и широко используемыми на практике, являются:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).$

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

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

$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 , среднее количество сравнений по всем перестановкам входной последовательности можно точно оценить, решив рекуррентное соотношение:

$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)$

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

$nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)$

$nC(n)=(n+1)C(n-1)+2n-2$

${\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, когда вставленные значения $(x_{1},x_{2},\ldots ,x_{n})$ образуют случайную перестановку.

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

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

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

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

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

$\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 ) .

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

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

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

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

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

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

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

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

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

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

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

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

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

Варианты

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

Вместо разделения на два подмассива с использованием одной опорной точки можно использовать быструю сортировку с несколькими опорными точками (также мультибыструю сортировку). ) делит входные данные на некоторое количество подмассивов, используя s - 1 поворотов. Хотя случай с двумя поворотами ( s = 3 ) рассматривался Седжвиком и другими еще в середине 1970-х годов, полученные алгоритмы на практике были не быстрее, чем «классическая» быстрая сортировка. Оценка мультибыстрой сортировки с переменным числом поворотов, проведенная в 1999 году и настроенная на эффективное использование кэша процессора, показала, что она увеличивает количество инструкций примерно на 20%, но результаты моделирования показали, что она будет более эффективной при очень больших входных данных. Версия быстрой сортировки с двумя шарнирами, разработанная Ярославским в 2009 году. оказалось достаточно быстрым для гарантированной реализации в Java 7 в качестве стандартного алгоритма сортировки массивов примитивов (сортировка массивов объектов выполняется с помощью Timsort ). Впоследствии выяснилось, что преимущество этого алгоритма в производительности в основном связано с производительностью кэша. Результаты экспериментов показывают, что вариант с тремя шарнирами может работать еще лучше на современных машинах.

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

Для дисковых файлов возможна внешняя сортировка на основе разделения, аналогичная быстрой сортировке. Это медленнее, чем внешняя сортировка слиянием, но не требует дополнительного дискового пространства. Используются 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(\log _{2}(n))$, сначала обрабатывается меньший подфайл. Для автономного стека поместите в стек параметры большего подфайла и выполните итерацию по меньшему подфайлу. Для рекурсии сначала выполните рекурсию по меньшему подфайлу, а затем выполните итерацию для обработки большего подфайла. Если количество записей в подфайле меньше или равно 4 B, он сортируется на месте с помощью быстрой сортировки и записывается. Теперь этот подфайл отсортирован и находится на своем месте в файле. Процесс продолжается до тех пор, пока все подфайлы не будут отсортированы и размещены на своих местах. Среднее количество проходов по файлу составляет примерно ${\frac {1+\ln(N+1)}{(4B)}}$, но в худшем случае $N$ проходит (эквивалентно $O(n^{2})$ для худшего случая внутренняя сортировка).

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

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

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

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

Также разработан Пауэрсом как 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 . См. Силы для дальнейшего обсуждения скрытых накладных расходов при сравнении, поразрядной и параллельной сортировке.

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

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

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

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

Основная статья: Частичная сортировка

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

Обобщение

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

См. также

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

Ссылки

• Седжвик, Р. (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 — подробное описание для начинающих