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

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

Анимированная визуализация алгоритма быстрой сортировки. Горизонтальные линии - это значения разворота.
Учебный класс	Алгоритм сортировки
Пессимистический производительность	О ( п 2 )
Лучшая производительность	O ( n log n ) (простой раздел) или O ( n ) (трехсторонний раздел и одинаковые ключи)
Средняя производительность	O ( п войти п )
Сложность пространства в наихудшем случае	O ( n ) вспомогательный (наивный) O (log n ) вспомогательный (Hoare 1962)

Quicksort - это эффективный алгоритм сортировки . Разработанный британским ученым-компьютерщиком Тони Хоаром в 1959 году ^[1] и опубликованный в 1961 году ^[2], этот алгоритм до сих пор широко используется для сортировки. При правильной реализации он может быть несколько быстрее, чем сортировка слиянием, и примерно в два или три раза быстрее, чем heapsort . ^{[3] [ противоречиво ]}

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

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

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

История [ править ]

Алгоритм быстрой сортировки был разработан в 1959 году Тони Хоаром, когда он был приглашенным студентом в МГУ . В то время Хоар работал над проектом машинного перевода для Национальной физической лаборатории . В процессе перевода ему нужно было отсортировать слова в русских предложениях, прежде чем искать их в русско-английском словаре, который был в алфавитном порядке на магнитной ленте . ^[5] Поняв, что его первая идея, сортировка вставкой , будет медленной, он придумал новую идею. Он написал часть раздела в Mercury Autocodeно возникли проблемы со списком несортированных сегментов. По возвращении в Англию его попросили написать код для Shellsort . Хоар упомянул своему боссу, что он знает о более быстром алгоритме, и его босс поставил шесть пенсов, что он не знает. Его босс в конце концов согласился, что он проиграл пари. Позже Хоар узнал об Алголе и его способности выполнять рекурсию, что позволило ему опубликовать код в Communications of the Association for Computing Machinery , главном журнале по информатике того времени. ^{[2] [6]}

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

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

В 2009 году Владимир Ярославский предложил новую реализацию Quicksort, использующую две точки поворота вместо одной. ^[11] В списках рассылки основной библиотеки Java он инициировал обсуждение, утверждая, что его новый алгоритм превосходит метод сортировки библиотеки времени выполнения, который в то время основывался на широко используемом и тщательно настроенном варианте классической быстрой сортировки Бентли и Макилроя. . ^[12] Quicksort Ярославского был выбран в качестве нового алгоритма сортировки по умолчанию в библиотеке времени выполнения Oracle Java 7 ^[13] после обширных эмпирических тестов производительности. ^[14]

Алгоритм [ править ]

Quicksort - это алгоритм «разделяй и властвуй» . Сначала он делит входной массив на два меньших подмассива: нижние элементы и высокие элементы. Затем он рекурсивно сортирует подмассивы. Шаги для быстрой сортировки на месте :

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

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

Шаги выбора точки поворота и разделения можно выполнить несколькими способами; выбор конкретных схем реализации сильно влияет на производительность алгоритма.

Схема разбиения Ломуто [ править ]

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

алгоритм быстрой сортировки (A, lo, hi) :  если lo <hi, то p: = раздел (A, lo, hi) быстрая сортировка (A, lo, p - 1) быстрая сортировка (A, p + 1, привет)Алгоритм раздела (А вот, привет) является pivot: = A [привет] я: = вот for j: = lo to hi do  if A [j] <pivot then поменять местами A [i] на A [j] я: = я + 1 поменять местами A [i] на A [привет] вернуться я

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

Схема разделения Хора [ править ]

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

алгоритм быстрой сортировки (A, lo, hi) :  если lo <hi, то p: = раздел (A, lo, hi) быстрая сортировка (A, lo, p) быстрая сортировка (A, p + 1, привет)Алгоритм раздела (А вот, привет) является точка поворота: = A [этаж ((привет + низ) / 2)] я: = lo - 1 j: = привет + 1 цикл навсегда  делать я: = я + 1 пока A [i] <pivot do j: = j - 1 в то время как A [J]> шарнир , если я ≥ J , то  возвращение J поменять местами A [i] на A [j]

Вращение деления округляется вниз, как показано здесь floorфункцией; ^[19] это позволяет избежать использования A [hi] в качестве точки поворота, что может привести к бесконечной рекурсии.

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

Проблемы реализации [ править ]

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

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

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

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

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

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

ninther ( a ) = медиана (Mo3 (первая из a ), Mo3 (средняя из a ), Mo3 (последняя из a ))

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

Повторяющиеся элементы [ править ]

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

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

алгоритм быстрой сортировки (A, lo, hi) :  если lo <hi, то p: = pivot (A, lo, hi) left, right: = partition (A, p, lo, hi) // примечание: несколько возвращаемых значений быстрая сортировка (A, lo, left - 1) быстрая сортировка (A, вправо + 1, привет)

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

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

Оптимизация [ править ]

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

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

Распараллеливание [ править ]

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

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

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

Формальный анализ [ править ]

Анализ наихудшего случая [ править ]

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

Если это происходит неоднократно в каждом разделе, то каждый рекурсивный вызов обрабатывает список размером на единицу меньше, чем предыдущий список. Следовательно, мы можем сделать n - 1 вложенных вызовов, прежде чем достигнем списка размером 1. Это означает, что дерево вызовов представляет собой линейную цепочку из n - 1 вложенных вызовов. Я й вызов делает O ( п - я ) работу , чтобы сделать раздел, и , таким образом , в этом случае Quicksort занимает O ( п ²) время.${\ displaystyle \ textstyle \ sum _ {я = 0} ^ {n} (ni) = 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 элементов с равной вероятностью . Мы перечисляем здесь три общих доказательства этого утверждения, дающих различное представление о работе быстрой сортировки.

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

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

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

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

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

${\ Displaystyle Т (п) = О (п) + Т (0) + Т (п-1) = О (п) + Т (п-1).}$

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

В наиболее сбалансированном случае один вызов быстрой сортировки включает 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 до п - 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₂ ( п !) Сравнения в среднем для сортировки п элементов (как описано в статье Сравнение рода ) и в случае больших п , Формула Стирлинга Урожайность log₂ ( п !) ≈ п (log₂ п - log₂ д ), поэтому быстрая сортировка не намного хуже, чем идеальная сортировка для сравнения. Это быстрое среднее время выполнения - еще одна причина практического превосходства быстрой сортировки над другими алгоритмами сортировки.

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

Следующее двоичное дерево поиска (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 ) . ^{[20] [23]}

Быстрая сортировка с локальным и нестабильным разделением использует только постоянное дополнительное пространство перед выполнением любого рекурсивного вызова. Quicksort должен хранить постоянный объем информации для каждого вложенного рекурсивного вызова. Поскольку в лучшем случае выполняется не более 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 ) пространство для рабочего хранилища и может реализовать стабильную сортировку. Рабочее хранилище позволяет легко и стабильно разбивать входной массив, а затем копировать обратно во входной массив для последовательных рекурсивных вызовов. Оптимизация Седжвика по-прежнему актуальна.

Отношение к другим алгоритмам [ править ]

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

Самый прямой конкурент быстрой сортировки - это heapsort . Время работы heapsort составляет O ( n log n ) , но среднее время работы heapsort обычно считается медленнее, чем быстрая сортировка на месте. ^[30] Этот результат спорен; некоторые публикации указывают на обратное. ^{[31] [32]} Introsort - это вариант быстрой сортировки, который переключается на heapsort при обнаружении плохого случая, чтобы избежать наихудшего времени работы быстрой сортировки.

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

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

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

Поворот на основе выбора [ править ]

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

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

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

Варианты [ править ]

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

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

Внешняя быстрая сортировка [ править ]

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

Трехсторонняя быстрая сортировка по основанию системы счисления [ править ]

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

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

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

BlockQuicksort [ править ]

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

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

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

Обобщение [ править ]

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Седжвик, Р. (1978). «Реализация программ Quicksort». Comm. ACM . 21 (10): 847–857. DOI : 10.1145 / 359619.359631 . S2CID  10020756 .
• Дин, Британская Колумбия (2006). «Простой анализ ожидаемого времени выполнения для рандомизированных алгоритмов« разделяй и властвуй »». Дискретная прикладная математика . 154 : 1–5. DOI : 10.1016 / j.dam.2005.07.005 .
• Хоар, ЦАР (1961). «Алгоритм 63: Разделение». Comm. ACM . 4 (7): 321. DOI : 10,1145 / 366622,366642 . S2CID  52800011 .
• Хоар, ЦАР (1961). «Алгоритм 65: Найти». Comm. ACM . 4 (7): 321–322. DOI : 10.1145 / 366622.366647 .
• Хоар, ЦАР (1962). «Быстрая сортировка» . Comput. J. 5 (1): 10–16. DOI : 10.1093 / comjnl / 5.1.10 .(Перепечатано в Hoare and Jones: Essays in computing science , 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. 
• Фарон Моллер . Анализ Quicksort . CS 332: Разработка алгоритмов. Департамент компьютерных наук Университета Суонси .
• Мартинес, К .; Роура, С. (2001). «Оптимальные стратегии выборки в Quicksort и Quickselect». SIAM J. Comput. 31 (3): 683–705. CiteSeerX  10.1.1.17.4954 . DOI : 10,1137 / S0097539700382108 .
• Bentley, JL; Макилрой, доктор медицины (1993). «Разработка функции сортировки». Программное обеспечение: практика и опыт . 23 (11): 1249–1265. CiteSeerX  10.1.1.14.8162 . DOI : 10.1002 / spe.4380231105 .

Внешние ссылки [ править ]

Реализация алгоритма Викибука имеет страницу на тему: Быстрая сортировка

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