SRT Поиск и сортировка Алгоритм
Быстрая сортировка
Также: Quicksort · сортировка Хоара · qsort · разбиение Хоара · разбиение Ломуто · introsort
Выбрать опорный элемент, разложить остальные на меньшие и большие и повторить для каждой части. На случайных данных это одна из самых быстрых сортировок, но у неё есть уязвимость: уже отсортированный вход, одинаковые ключи и подобранный противником порядок превращают n log n в n². Как она ломается и как её защищают в стандартных библиотеках.
Вот тысяча последних землетрясений каталога USGS. Отсортируем их по силе учебной быстрой сортировкой, где опорным берётся первый элемент куска: 16 628 сравнений. Теперь отсортируем их ещё раз — вход уже упорядочен, работы вроде бы нет совсем: 501 498 сравнений, в тридцать раз больше. Возьмите в роли опорного средний элемент, и отсортированный вход перестанет пугать. Но для любого такого правила найдётся свой убийца: порядок, подобранный противником, который подсматривает за сравнениями. Попробуйте все правила на всех трёх входах.
Сводка по тысяче землетрясений, разбиение Хоара:
| Опорный | Как в каталоге | Уже по силе | Убийца |
|---|---|---|---|
| первый | 16 628 | 501 498 | 501 498 |
| средний | 15 382 | 11 804 | 501 498 |
| медиана трёх | 16 324 | 13 802 | 256 490 |
| случайный | 14 864 | 14 106 | 501 498, а с новой монеткой — 14 229 |
Для сравнения: n log₂ n ≈ 9966, n²/2 = 500 000. Последняя строка — главное в этой статье. Случайный выбор опорного не спасает от противника, который видит броски монетки во время сортировки. Но настоящий противник присылает данные заранее, а монетку бросают потом — и тогда подобранный им порядок ничем не хуже обычного.
Идея
Выберем любой элемент — опорный — и переставим остальные так, чтобы меньшие оказались левее него, а большие правее. Опорный встал на своё окончательное место, и две части можно сортировать независимо, тем же способом. Склеивать ничего не нужно: всё левое уже меньше всего правого.
У сортировки слиянием всё наоборот: она режет массив вслепую, ровно пополам, а думает при склейке. Быстрая сортировка думает при разрезании и не склеивает. Плата за это — неровный разрез: если опорный оказался почти самым маленьким, одна часть пустая, а другая почти такая же, как была, и работа на этом уровне потрачена почти впустую.
Разбиение
Вся работа быстрой сортировки — в разбиении. Классических способов два.
Хоар (1961). Опорный ставим в начало куска, два указателя идут навстречу: i слева останавливается на элементе не меньше опорного, j справа — на элементе не больше. Оба стоят «не на своей стороне» — меняем их местами и идём дальше. Когда указатели встретились, всё левее j включительно не больше опорного, всё правее — не меньше. Обменов немного: меняются только пары, которые обе стоят не там.
Ломуто. Опорный ставим в конец, один указатель j идёт слева направо, а всё, что меньше опорного, по очереди переставляется в начало, за указатель i. В конце опорный меняется с элементом на месте i. Код короче и его проще доказать, поэтому этот вариант любят учебники: его популяризировал Джон Бентли в «Жемчужинах программирования», сославшись на Нико Ломуто, а за ним — учебник Кормена и соавторов.
Ниже — оба на двадцати сильнейших землетрясениях 2025 года и третий способ, разбиение на три части. Обратите внимание на одинаковые магнитуды: в этом маленьком массиве по четыре землетрясения силой 6,9 и 7,4.
Посмотрите на нижнюю панель. На всех 2128 землетрясениях 2025 года Хоару понадобилось 28 537 сравнений, Ломуто — 339 623, в двенадцать раз больше, а рекурсия ушла на глубину 549. На всём каталоге разница больше: 326 тысяч сравнений против 24,8 миллиона. Виноваты одинаковые ключи. Магнитуды записывают с одним знаком после запятой, и сила 5,0 встречается в 2025 году 547 раз. Ломуто отправляет все элементы, равные опорному, в одну сторону, и кусок из k одинаковых чисел он разбивает на 0 и k − 1 — это квадрат, k²/2 сравнений. Хоар останавливает оба указателя на равных опорному и меняет их местами, поэтому одинаковые делятся между частями поровну, и квадрата нет.
Третий способ ещё лучше: разбиение на три части. Слева собираются меньшие опорного, справа — большие, а равные остаются посередине и в рекурсию больше не попадают. На каталоге это 103 тысячи сравнений: чем больше повторов, тем меньше работы. Эту схему Эдсгер Дейкстра описал как задачу о трёхцветном флаге — разложить три цвета за один проход, — а в стандартную функцию сортировки её встроили Бентли и Макилрой в 1993 году. Попробуйте её в задаче о трёх классах глубины.
Почему в среднем n log n
Если каждый раз опорный делит кусок пополам, уровней рекурсии log₂ n, и на каждом уровне все элементы сравниваются с опорными своих кусков — n log₂ n, как у слияния. Но пополам выходит редко. Важнее другое: даже совершенно случайный опорный в среднем почти не хуже.
Пусть элементы различны, опорный в каждом куске выбирается случайно и равновероятно, и при разбиении каждый элемент куска сравнивается с опорным один раз. Тогда среднее число сравнений на любом входе равно 2(n + 1)Hn − 4n ≈ 2n ln n ≈ 1,39 n log₂ n, где Hn = 1 + 1/2 + … + 1/n.
Обозначим элементы в порядке возрастания z₁ < z₂ < … < zn. Два элемента сравниваются, только если один из них опорный, а опорный после разбиения в рекурсию не идёт, — значит, каждая пара сравнивается не больше одного раза.
Возьмём пару zi и zj, i < j, и посмотрим на отрезок zi, zi+1, …, zj из j − i + 1 элементов. Пока опорными выбираются элементы вне этого отрезка, он целиком попадает в одну часть. Рано или поздно опорным станет какой-то его элемент. Если это zi или zj — пара сравнится. Если кто-то между ними — zi и zj разъедутся по разным частям и не встретятся никогда. Все элементы отрезка имеют равные шансы оказаться первым опорным, поэтому пара сравнивается с вероятностью 2/(j − i + 1).
Среднее число сравнений — сумма этих вероятностей по всем парам. Пар с разностью d = j − i ровно n − d, поэтому сумма равна 2 Σk=2..n (n − k + 1)/k = 2(n + 1)Hn − 4n, а Hn ≈ ln n.
Обратите внимание на слово «любом». Среднее берётся по броскам монетки, а не по входам: никакой вход не плох всегда, плохими бывают только неудачные броски, а они редки. Разбиение Хоара делает чуть больше сравнений, чем в теореме: указатели заходят друг за друга, и пара элементов у места встречи сравнивается с опорным дважды. На тысяче землетрясений теорема обещает 10 986 сравнений, у Хоара их 14 864.
Худший случай и атака
Худший случай быстрой сортировки — когда опорный раз за разом оказывается крайним: части 0 и k − 1, глубина рекурсии n, сравнений около n²/2. С правилом «первый элемент» его даёт уже отсортированный массив — а сортировать отсортированное приходится постоянно: вчерашний каталог с парой новых строк, результат прошлой сортировки, данные из другой системы, где их уже упорядочили. Правило «средний элемент» отсортированный вход переносит отлично, медиана первого, среднего и последнего — тоже. Значит ли это, что худший случай стал редкостью?
Нет, и это показал Дуглас Макилрой в заметке «A Killer Adversary for Quicksort» (1999). Его противник ничего не знает об устройстве сортировки: он подставляет ей свою функцию сравнения и придумывает данные на ходу. Сначала у всех элементов значения нет — Макилрой называет их «газом». Застывший элемент всегда меньше газа. Когда сравниваются два газа, один из них застывает и получает следующее по величине значение, причём противник старается заморозить того, кто похож на опорный, — газ, который последним пережил сравнение. Опорный участвует в каждом сравнении разбиения, поэтому застывает первым, оказывается меньше всех остальных, и разбиение отрезает от куска один-два элемента. Когда сортировка закончена, застывшие значения и есть вход, на котором она квадратична, — причём это перестановка, без противоречий.
Противник одинаково ломает и «первый», и «средний», и медиану трёх: в таблице выше это 501 498, 501 498 и 256 490 сравнений. Медиана трёх продержалась вдвое дольше, но квадрата не избежала. Макилрой проверил своего противника на qsort из нескольких тогдашних систем — квадрат получился у всех, даже у сортировки Бентли и Макилроя, которая выбирает опорный по девяти элементам. Пройти через его противника можно только одним способом: выбирать опорный так, чтобы противник не мог предсказать выбор. Если монетку бросают уже после того, как вход прислан, вход, подобранный под прошлые броски, работает как обычные данные: 14 229 сравнений вместо 501 498.
Это не только теория. На соревнованиях Codeforces участники «взламывают» чужие решения тестами, и решения на Java, сортировавшие массив int[] через Arrays.sort, годами валились на специально подобранных массивах: быстрая сортировка для чисел там детерминирована. Обычный совет в таких обсуждениях — перемешать массив перед сортировкой или сортировать объекты, для которых Java использует слияние. Попробуйте построить такой вход сами в задаче «Сломайте быструю сортировку».
Как защищаются библиотеки
Случайный опорный защищает в среднем, но не даёт гарантии: неудачные броски маловероятны, а не невозможны. Библиотекам нужна гарантия, и её дал Дэвид Массер в 1997 году — интроспективная сортировка, introsort. Это обычная быстрая сортировка, которая следит за глубиной рекурсии. Если глубина превысила примерно 2 log₂ n, значит, разбиения идут плохо, и оставшийся кусок досортировывается пирамидальной сортировкой, у которой худший случай — n log n. На обычных данных ограничитель не срабатывает никогда, и сортировка работает как быстрая.
Так устроена std::sort в стандартной библиотеке GCC: медиана трёх в роли опорного, предел глубины 2⌊log₂ n⌋, куски до 16 элементов досортировываются в конце вставками. Go с версии 1.19 сортирует pdqsort — «быструю сортировку, побеждающую шаблоны» Орсона Питерса: она замечает неудачные разбиения, перемешивает подозрительные куски и тоже держит в запасе пирамидальную сортировку. В Java массивы чисел сортирует быстрая сортировка с двумя опорными элементами, а в свежих версиях JDK и она при слишком глубокой рекурсии переходит на пирамидальную.
Код
Версия, близкая к той, что пишут в настоящих программах: случайный опорный и разбиение Хоара. Есть и ещё одна деталь: рекурсия уходит только в меньшую из двух частей, а большую доделывает цикл. Меньшая часть не больше половины куска, поэтому глубина стека не превышает log₂ n даже при самых неудачных опорных. Без этого приёма на плохом входе рекурсия ушла бы на глубину n — в Python это RecursionError уже на тысяче элементов. Генератор случайных чисел свой, чтобы Python и Go выбирали одни и те же опорные.
Обратите внимание на вывод: равные элементы перепутаны. Быстрая сортировка неустойчива — дальние обмены разбиения переставляют равные как попало:
7.4: 09-13 07-20 10-10 05-02 <- out of date order
Три схемы разбиения на всех землетрясениях 2025 года — те же числа, что в нижней панели второй сцены:
И противник Макилроя. Вся его хитрость умещается в функцию сравнения из десятка строк, а сортировка, которую он атакует, о нём ничего не знает:
Сколько это стоит
| Сравнений | Когда | |
|---|---|---|
| лучший случай | около n log₂ n | каждый опорный делит кусок пополам |
| в среднем, случайный опорный | ≈ 1,39 n log₂ n | на любом входе |
| худший случай | около n²/2 | опорный каждый раз крайний |
Память — только стек рекурсии: O(log n), если рекурсия идёт в меньшую часть, и до O(n) без этого приёма. Буфер, как у слияния, не нужен — быстрая сортировка работает на месте. Замер на Python и Go: случайный опорный на случайных и на уже отсортированных данных, первый элемент в роли опорного на отсортированных и встроенная сортировка.
У первого элемента на отсортированном входе наклон 2 — квадрат во всей красе. Случайный опорный держит наклон чуть больше единицы на любом входе. На Go наша быстрая сортировка на миллионе чисел даже обгоняет slices.Sort, а на отсортированном входе работает быстрее, чем на случайном: обменов почти нет, и процессор легко предсказывает ветвления. На Python встроенная сортировка, написанная на C, впереди примерно в двадцать раз.
Почему быструю сортировку так любят, если сравнений у неё больше, чем у слияния? На шестнадцати землетрясениях из демо выше ей понадобилось 98 сравнений против 46 у слияния. Дело в остальной работе. Разбиение идёт по массиву подряд, внутренний цикл — сравнение и сдвиг указателя, обменов мало, лишней памяти нет, и всё, с чем она работает, лежит рядом в кэше процессора. На числах в памяти это обычно перевешивает лишние сравнения. Там, где сравнение дорого или нужна устойчивость, выигрывает слияние — поэтому Python и сортирует слиянием.
Словарь на магнитной ленте
В 1959 году Тони Хоар, изучавший классические языки и философию, стажировался в университете и взялся за машинный перевод. Русско-английский словарь хранился на магнитной ленте по алфавиту, и слова переводимого предложения выгодно было сначала отсортировать — тогда их все можно найти за один проход ленты. Как Хоар вспоминал в интервью журналу Communications of the ACM, первым ему пришёл в голову способ, который теперь называют пузырьком, и он отверг его как слишком медленный. Вторым был quicksort.
В 1960 году Хоар поступил программистом в фирму Elliott Brothers, и первым заданием было написать подпрограмму сортировки по только что опубликованному методу Шелла. В тьюринговской лекции 1980 года он рассказал, что сделал её, а потом робко сказал начальнику, Пату Шеклтону, что придумал способ, который обычно работает быстрее. Тот поспорил на шесть пенсов, что нет. Объяснить метод было очень трудно, но начальник в конце концов признал, что спор проигран. Записать алгоритм коротко Хоару помогла рекурсия: на Пасху 1961 года он попал на курсы по языку Алгол 60, которые вели Петер Наур, Эдсгер Дейкстра и Питер Ландин, и там написал процедуру, «нескромно названную QUICKSORT». В июле 1961 года журнал Communications of the ACM напечатал три его алгоритма подряд: Partition, Quicksort и Find, будущий быстрый выбор, а в 1962 году вышла большая статья в The Computer Journal.
Премию Тьюринга Хоар получил в 1980 году — за вклад в определение и устройство языков программирования. Он умер 5 марта 2026 года в возрасте 92 лет. Его сортировка в разных вариантах до сих пор работает в стандартных библиотеках многих языков.
Задачи
Первая — разбиение на три части, то самое, что спасает быструю сортировку от одинаковых ключей. Вторая — атака: постройте вход, на котором заданная быстрая сортировка тратит квадрат.
Три класса глубины Сломайте быструю сортировкуДанные: Землетрясения: каталог USGS, общественное достояние