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

В прошлом уроке ты увидел общую карту мира сортировок: от наивного пузырька с его $O(n^2)$ до алгоритмов, работающих за $O(n \log n)$. Среди последних быстрая сортировка (QuickSort) занимает особое место — не потому что она единственная с такой асимптотикой, а потому что именно она чаще всего скрывается за вызовом sort() в реальном коде. Встроенная сортировка массивов чисел в языке C, значительная часть внутренней логики std::sort в C++, сортировка примитивных типов в Java — всё это в основе своей варианты быстрой сортировки. Разобраться в её механике — значит разобраться не в абстрактной задаче из учебника, а в алгоритме, который прямо сейчас выполняется миллиарды раз в секунду на серверах по всему миру.

Идея, на которой строится быстрая сортировка, — рекурсивное разбиение данных по одному выбранному элементу — прямо предвосхищает конструкцию, с которой ты обязательно столкнёшься в машинном обучении: построение дерева решений. Когда дерево решений строит очередной узел, оно выбирает признак и порог и делит обучающую выборку на две части: объекты, у которых значение признака меньше порога, и объекты, у которых оно больше, — а затем рекурсивно повторяет ту же процедуру на каждой из получившихся частей. Быстрая сортировка делает структурно то же самое: выбирает опорный элемент (pivot), делит массив на «меньше pivot» и «больше pivot», а затем рекурсивно сортирует каждую часть независимо. Оба процесса — это рекурсивное разбиение данных по критерию, применённое снова и снова, пока не останутся тривиальные, неделимые кусочки. Разница лишь в том, что именно оптимизируется на каждом шаге — порядок элементов в одном случае, чистота классов в другом, — но сам скелет рекурсии идентичен.

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

В этом уроке ты подробно разберёшь: как устроена рекурсия «разделяй и властвуй» и какие есть стратегии выбора опорного элемента, как физически происходит разбиение массива (partition) — та самая процедура, в которой сосредоточена почти вся работа алгоритма, почему один и тот же алгоритм может отработать за $O(n \log n)$ на одних данных и деградировать до $O(n^2)$ на других, и что вообще значит «сортировка на месте» и почему быстрая сортировка не сохраняет исходный порядок равных элементов. Все четыре темы связаны в одну логическую цепочку: от идеи — к её реализации — к анализу производительности — к практическим ограничениям, о которых нужно помнить, применяя алгоритм в реальном коде.

История: как Тони Хоар придумал алгоритм ради словаря

В 1959 году молодой британский математик Чарльз Энтони Ричард Хоар (Tony Hoare) работал в Москве — он участвовал в проекте по машинному переводу с русского языка на английский, а параллельно учился на аспирантском курсе теории вероятностей и статистики под руководством Андрея Николаевича Колмогорова в Московском государственном университете. Задача, которая привела его к изобретению будущего алгоритма, была совсем не академической: программе машинного перевода требовалось быстро искать русские слова в отсортированном словаре, а для этого сначала нужно было эффективно отсортировать сам словарь. Хоар искал способ сделать это быстрее, чем существовавшие на тот момент простые методы сортировки, работавшие за квадратичное время.

Идея, которая пришла ему в голову, была обманчиво простой: вместо того чтобы последовательно сравнивать пары соседних элементов, как это делают простые методы, можно выбрать один элемент как «опорный», одним проходом переставить все элементы массива так, чтобы всё меньшее опорного оказалось слева, а всё большее — справа, и затем рекурсивно применить ту же процедуру к каждой из двух частей. Хоар реализовал первую версию алгоритма на языке Mercury Autocode для компьютера Ferranti Mercury, а по возвращении в Великобританию формализовал идею и в 1961 году опубликовал в журнале Communications of the ACM два коротких алгоритма — «Algorithm 63: Partition» и «Algorithm 64: Quicksort», — а годом позже, в 1962-м, подробную статью «Quicksort» в журнале The Computer Journal, где впервые дал полный анализ сложности алгоритма в среднем и в худшем случае.

Хоар не остановился на быстрой сортировке — он же изобрёл алгоритм QuickSelect для поиска k-го по порядку элемента (используя ту же идею partition, но без рекурсии в обе стороны), разработал аксиоматическую семантику программ (логику Хоара, до сих пор фундаментальную для формальной верификации кода) и в 1980 году получил премию Тьюринга — главную награду в информатике — за фундаментальный вклад в определение и проектирование языков программирования. Несмотря на то что с момента публикации алгоритма прошло больше шестидесяти лет, а компьютеры с тех пор изменились до неузнаваемости, сама идея разбиения массива вокруг опорного элемента оказалась настолько удачной, что легла в основу гибридных алгоритмов сортировки, используемых в стандартных библиотеках практически всех массовых языков программирования и по сей день.

Идея «разделяй и властвуй» и выбор опорного элемента

Интуиция

Представь, что тебе нужно рассадить учеников класса по росту, но вместо того чтобы сравнивать каждого с каждым, ты выбираешь одного ученика — например, того, кто стоит последним в очереди, — и просишь весь класс разделиться на две группы: тех, кто ниже выбранного ученика, и тех, кто выше. Сам выбранный ученик встаёт строго между группами. Дальше внутри группы «ниже» ты повторяешь тот же трюк — выбираешь ещё одного ученика внутри этой группы и снова делишь её пополам, и то же самое делаешь с группой «выше». Продолжаешь до тех пор, пока в каждой подгруппе не останется один человек или вообще никого — такую подгруппу уже не нужно делить, она тривиально «отсортирована». Когда рекурсия закончится на всех ветках, весь класс окажется выстроен по росту, причём без единого шага «слияния» в конце — сам процесс разбиения уже расставил всех по нужным местам.

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

Алгоритм

QuickSort(A, lo, hi):

1. Если lo >= hi — вернуться (подмассив из 0 или 1 элемента уже отсортирован, это базовый случай рекурсии).
2. Выбрать опорный элемент (pivot) одним из способов: первый элемент подмассива, последний элемент, случайно выбранный элемент, либо медиана трёх заранее отобранных элементов (обычно первого, среднего и последнего).
3. Вызвать Partition(A, lo, hi) — переставить элементы подмассива так, чтобы всё, что $\le$ pivot, оказалось левее некоторого индекса $p$, а всё, что $>$ pivot, — правее; функция возвращает финальный индекс pivot $p$.
4. Рекурсивно вызвать QuickSort(A, lo, p - 1).
5. Рекурсивно вызвать QuickSort(A, p + 1, hi).

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

Примеры с разбором

Пример 1. Наивная реализация и полная трассировка рекурсии. Для наглядности на этом шаге удобно рассмотреть не in-place версию (её разберём в следующем разделе), а упрощённую, создающую новые списки — она честно показывает саму структуру рекурсии, не отвлекая на детали перестановок индексов.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]                       # стратегия: первый элемент
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quicksort(left) + [pivot] + quicksort(right)

Применим к массиву $[5, 2, 8, 1, 9, 3]$.

Уровень 0: pivot $= 5$. Оставшиеся элементы $2, 8, 1, 9, 3$ делятся на left $= [2, 1, 3]$ (те, что $\le 5$) и right $= [8, 9]$ (те, что $> 5$).

Уровень 1 (ветка left): для $[2, 1, 3]$ pivot $= 2$. Остаток $1, 3$ делится на left $= [1]$, right $= [3]$. Оба — базовый случай, возвращаются как есть. Результат ветки: $[1] + [2] + [3] = [1, 2, 3]$.

Уровень 1 (ветка right): для $[8, 9]$ pivot $= 8$. Остаток $9$ целиком $> 8$, значит left $= []$, right $= [9]$. Результат ветки: $[] + [8] + [9] = [8, 9]$.

Сборка на уровне 0: $[1, 2, 3] + [5] + [8, 9] = [1, 2, 3, 5, 8, 9]$.

Дерево рекурсии в этом прогоне получилось несимметричным: левая ветка потребовала ещё одного уровня деления, правая — нет, итоговая глубина рекурсии равна $2$.

Пример 2. Тот же массив, но другая стратегия выбора pivot. Возьмём тот же массив $[5, 2, 8, 1, 9, 3]$, но выберем pivot как последний элемент подмассива на каждом уровне.

Уровень 0: pivot $= 3$ (последний элемент). Остаток $5, 2, 8, 1, 9$ делится на left $= [2, 1]$ (то, что $\le 3$), right $= [5, 8, 9]$ (то, что $> 3$).

Уровень 1 (ветка left): для $[2, 1]$ pivot $= 1$ (последний). Остаток $2$ целиком $> 1$: left $= []$, right $= [2]$. Результат: $[1, 2]$.

Уровень 1 (ветка right): для $[5, 8, 9]$ pivot $= 9$ (последний). Остаток $5, 8$ целиком $\le 9$: left $= [5, 8]$, right $= []$. Результат ветки требует ещё одного уровня.

Уровень 2 (внутри right от right): для $[5, 8]$ pivot $= 8$ (последний). Остаток $5 \le 8$: left $= [5]$, right $= []$. Результат: $[5, 8]$.

Сборка: правая ветка целиком даёт $[5, 8, 9]$, левая — $[1, 2]$. Итог: $[1, 2] + [3] + [5, 8, 9] = [1, 2, 3, 5, 8, 9]$.

Результат совпал с примером 1 — это ожидаемо, ведь корректность алгоритма не зависит от стратегии выбора pivot. А вот форма дерева рекурсии изменилась: глубина выросла до $3$ вместо $2$, потому что на этот раз правая часть массива оказалась «неудачно» устроена относительно выбора «последний элемент» именно на этих конкретных числах. Один и тот же массив с разными стратегиями pivot порождает разные по форме деревья рекурсии — при одинаковом финальном результате.

Пример 3. Намёк на вырожденный случай: уже отсортированный массив. Возьмём массив $[1, 2, 3, 4, 5]$, уже отсортированный по возрастанию, и применим стратегию «pivot — первый элемент».

Уровень 0: pivot $= 1$. Все оставшиеся элементы $2, 3, 4, 5$ больше $1$: left $= []$, right $= [2, 3, 4, 5]$.

Уровень 1: pivot $= 2$. Остаток $3, 4, 5$ весь больше $2$: left $= []$, right $= [3, 4, 5]$.

Уровень 2: pivot $= 3$. Остаток $4, 5$ весь больше $3$: left $= []$, right $= [4, 5]$.

Уровень 3: pivot $= 4$. Остаток $5$ больше $4$: left $= []$, right $= [5]$.

Уровень 4: подмассив $[5]$ — базовый случай.

На каждом уровне ровно один элемент «отщепляется» как pivot, а всё остальное целиком уходит в правую часть. Дерево рекурсии выродилось в цепочку глубиной $4$ вместо ожидаемых $\lceil \log_2 5 \rceil = 3$ уровней при сбалансированном делении — и на массиве большего размера разрыв между «цепочкой» и «сбалансированным деревом» будет расти уже не линейно, а куда быстрее, о чём подробно пойдёт речь в разделе про худший случай.

Почему это важно

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

Разбиение массива (partition): сердце алгоритма

Интуиция

Наивная реализация из предыдущего раздела, создающая новые списки left и right на каждом уровне рекурсии, прекрасно иллюстрирует идею, но плоха с точки зрения практической эффективности: она расходует дополнительную память на копирование элементов и требует лишних проходов по данным. Промышленные реализации быстрой сортировки вместо этого переставляют элементы прямо внутри исходного массива — без единой дополнительной структуры для хранения копий. Эта операция называется разбиением на месте (in-place partition), и именно в ней сосредоточена практически вся реальная работа алгоритма — рекурсия лишь организует повторное применение partition к всё более мелким кускам массива.

Одна из самых распространённых практических реализаций — схема Ломуто (Lomuto partition scheme), названная в честь Ника Ломуто, который предложил её как более простую для понимания и реализации альтернативу оригинальной схеме самого Хоара. Идея: выбрать pivot (обычно последний элемент подмассива), затем одним проходом слева направо поддерживать границу между уже просмотренной «зоной меньше-или-равно» и ещё не просмотренной частью, перемещая элементы, оказавшиеся не больше pivot, в эту зону через своп. В самом конце остаётся единственный финальный своп, ставящий сам pivot на границу между двумя зонами.

Алгоритм

Partition-Lomuto(A, lo, hi):

1. $pivot \gets A[hi]$ (в качестве опорного берётся последний элемент подмассива).
2. $i \gets lo - 1$ (индекс — граница зоны «$\le pivot$», изначально зона пуста).
3. Для $j$ от $lo$ до $hi - 1$:
   • Если $A[j] \le pivot$: увеличить $i$ на $1$, поменять местами $A[i]$ и $A[j]$.
4. Поменять местами $A[i+1]$ и $A[hi]$ (поставить pivot на его финальное место, сразу за зоной «$\le pivot$»).
5. Вернуть $i + 1$ — финальный индекс pivot в массиве.

Существует и альтернативная схема — исходная схема Хоара (Hoare partition scheme), придуманная им ещё в 1961 году. В ней используются два указателя, стартующие с противоположных концов подмассива и движущиеся навстречу друг другу: левый ищет элемент, который больше pivot, правый — элемент, который меньше pivot, и как только оба находят такую пару, элементы меняются местами, после чего указатели продолжают движение. Схема Хоара в среднем делает примерно втрое меньше свопов, чем схема Ломуто, поскольку своп там происходит только при реальной необходимости обмена, а не на каждом шаге, где элемент просто оказался в «своей» зоне. Расплата — она не гарантирует, что после её завершения pivot окажется точно на границе разбиения (гарантируется лишь корректность самого разбиения в целом), из-за чего код чуть менее нагляден для объяснения на первом знакомстве с алгоритмом. Из-за большей прозрачности именно схему Ломуто чаще всего показывают при первом изучении алгоритма — и именно её мы разберём подробно на примерах ниже.

Примеры с разбором

Пример 1. Полная трассировка с несбалансированным pivot. Массив $A = [8, 3, 5, 4, 7, 6, 1, 2]$, $lo = 0$, $hi = 7$, $pivot = A[7] = 2$.

$i = -1$.

$j=0$: $A[0]=8$, $8 \le 2$? нет. $j=1$: $A[1]=3$, $3 \le 2$? нет. $j=2$: $A[2]=5$, $5 \le 2$? нет. $j=3$: $A[3]=4$, $4 \le 2$? нет. $j=4$: $A[4]=7$, $7 \le 2$? нет. $j=5$: $A[5]=6$, $6 \le 2$? нет. $j=6$: $A[6]=1$, $1 \le 2$? да $\to i=0$, своп $A[0] \leftrightarrow A[6]$: массив становится $[1, 3, 5, 4, 7, 6, 8, 2]$.

Цикл завершён ($j$ дошёл до $hi-1=6$). Финальный своп: $A[i+1] \leftrightarrow A[hi]$, то есть $A[1] \leftrightarrow A[7]$: значения $3$ и $2$ меняются местами — массив становится $[1, 2, 5, 4, 7, 6, 8, 3]$.

Возвращаемый индекс pivot: $i+1 = 1$. Проверка: $A[1] = 2$ — действительно pivot; слева от него $[1]$ — единственный элемент, и он $\le 2$; справа $[5, 4, 7, 6, 8, 3]$ — все они $> 2$. Разбиение оказалось крайне несбалансированным: всего один элемент оказался меньше pivot, шесть — больше. Это результат того, что pivot $=2$ был вторым по величине среди самых маленьких значений в массиве.

Пример 2. Полная трассировка с более сбалансированным pivot. Массив $A = [4, 7, 2, 1, 6, 3, 8, 5]$, $lo=0$, $hi=7$, $pivot = A[7] = 5$.

$i=-1$.

$j=0$: $A[0]=4 \le 5$? да $\to i=0$, своп $A[0]\leftrightarrow A[0]$ (без изменений). Массив: $[4,7,2,1,6,3,8,5]$. $j=1$: $A[1]=7 \le 5$? нет. $j=2$: $A[2]=2 \le 5$? да $\to i=1$, своп $A[1]\leftrightarrow A[2]$: массив $[4,2,7,1,6,3,8,5]$. $j=3$: $A[3]=1 \le 5$? да $\to i=2$, своп $A[2]\leftrightarrow A[3]$: массив $[4,2,1,7,6,3,8,5]$. $j=4$: $A[4]=6 \le 5$? нет. $j=5$: $A[5]=3 \le 5$? да $\to i=3$, своп $A[3]\leftrightarrow A[5]$: массив $[4,2,1,3,6,7,8,5]$. $j=6$: $A[6]=8 \le 5$? нет.

Цикл завершён. Финальный своп: $A[i+1]\leftrightarrow A[hi]$, то есть $A[4]\leftrightarrow A[7]$: значения $6$ и $5$ меняются местами — массив становится $[4,2,1,3,5,7,8,6]$.

Возвращаемый индекс pivot: $i+1=4$. Проверка: $A[4]=5$; слева $[4,2,1,3]$ — все $\le 5$; справа $[7,8,6]$ — все $>5$. Разбиение $4$ на $3$ — заметно сбалансированнее, чем в примере 1, хотя и не идеально пополам.

Пример 3. Массив с повторяющимися значениями. Массив $A = [4, 2, 4, 1, 4, 3]$, $lo=0$, $hi=5$, $pivot = A[5] = 3$.

$i=-1$.

$j=0$: $A[0]=4 \le 3$? нет. $j=1$: $A[1]=2 \le 3$? да $\to i=0$, своп $A[0]\leftrightarrow A[1]$: массив $[2,4,4,1,4,3]$. $j=2$: $A[2]=4 \le 3$? нет. $j=3$: $A[3]=1 \le 3$? да $\to i=1$, своп $A[1]\leftrightarrow A[3]$: массив $[2,1,4,4,4,3]$. $j=4$: $A[4]=4 \le 3$? нет.

Цикл завершён. Финальный своп: $A[i+1]\leftrightarrow A[hi]$, то есть $A[2]\leftrightarrow A[5]$: значения $4$ и $3$ меняются местами — массив становится $[2,1,3,4,4,4]$.

Возвращаемый индекс pivot: $i+1=2$. Проверка: $A[2]=3$; слева $[2,1]$ — оба $\le 3$; справа $[4,4,4]$ — все $>3$. Все три четвёрки корректно оказались в правой части, при этом относительный порядок между ними в данном конкретном прогоне случайно сохранился — но, как будет подробно показано в разделе про неустойчивость, полагаться на это нельзя: в других расположениях повторяющихся элементов их относительный порядок нарушается.

Почему это важно

Partition — это единственное место алгоритма, где вообще происходит какая-либо содержательная работа с данными: рекурсия сама по себе лишь организует, к каким подмассивам эту работу применить. Именно поэтому реальная скорость быстрой сортировки в первую очередь определяется тем, насколько эффективно реализован этот единственный линейный проход — минимизация числа сравнений и свопов здесь напрямую отражается на суммарном времени работы всего алгоритма. Тот же принцип — эффективный линейный проход, физически переставляющий индексы (а не копирующий сами объекты) вокруг выбранного порога, — используют и промышленные реализации построения узлов дерева решений в библиотеках вроде scikit-learn или XGBoost: при поиске лучшего разбиения выборки по признаку они переставляют массив индексов объектов, а не сами строки данных, экономя память и время ровно тем же способом, каким in-place partition экономит их в быстрой сортировке.

Худший и средний случай: почему всё решает выбор опорного элемента

Интуиция

Каждый вызов partition на подмассиве размера $m$ стоит $O(m)$ — это фиксированная плата за один линейный проход. Вопрос в том, сколько суммарной работы — потребуется по всем уровням рекурсии, а это целиком зависит от того, насколько сбалансированным получается каждое разбиение. Если pivot каждый раз оказывается примерно посередине подмассива, глубина дерева рекурсии — логарифмическая, $\log_2 n$ уровней, а суммарная работа на каждом уровне (по всем веткам вместе) равна $O(n)$ — итог $O(n \log n)$. Если же pivot каждый раз оказывается экстремумом (минимумом или максимумом подмассива), каждое разбиение уменьшает размер задачи лишь на единицу, число уровней рекурсии становится равным $n$, а не $\log_2 n$ — и итоговая сложность скатывается к $O(n^2)$.

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

Рекуррентное соотношение для сбалансированного случая: $T(n) = 2T(n/2) + O(n)$, откуда $T(n) = O(n \log n)$. Рекуррентное соотношение для худшего случая: $T(n) = T(n-1) + O(n)$, откуда $T(n) = O(n^2)$. Строгий результат для рандомизированной версии алгоритма (pivot выбирается случайно на каждом шаге): математическое ожидание числа сравнений равно $O(n \log n)$ для любого фиксированного входного массива без исключений — точная константа составляет примерно $2n\ln n \approx 1{,}39\, n \log_2 n$.

Разберём, откуда берутся эти оценки, через дерево рекурсии. В сбалансированном случае на уровне $0$ выполняется работа $O(n)$ (один вызов partition на весь массив). На уровне $1$ — два вызова, каждый на подмассиве размера примерно $n/2$, суммарная работа уровня $= 2 \cdot O(n/2) = O(n)$. На уровне $k$ — $2^k$ вызовов размера примерно $n/2^k$, суммарная работа уровня снова $O(n)$ — работа на каждом уровне одинакова, а число уровней до достижения размера подзадачи $1$ равно $\log_2 n$. Итог: $O(n) \times O(\log n) = O(n \log n)$.

В худшем случае дерево вырождается в цепочку: на уровне $0$ работа $O(n)$, на уровне $1$ — $O(n-1)$ (подзадача уменьшилась лишь на pivot), на уровне $2$ — $O(n-2)$, и так далее до уровня $n-1$. Здесь, в отличие от сбалансированного случая, работа на каждом уровне убывает линейно, но зато число уровней растёт линейно (а не логарифмически) — суммарная работа $O(n) + O(n-1) + \dots + O(1) = O\!\left(\frac{n(n+1)}{2}\right) = O(n^2)$.

Примеры с разбором

Пример 1. Точный подсчёт сравнений на вырожденном случае. Массив $[1, 2, \dots, 10]$, уже отсортированный по возрастанию, стратегия pivot $=$ первый элемент. На каждом уровне рекурсии из подмассива длины $m$ выделяется один pivot (минимум подмассива, поскольку массив изначально возрастает), а все остальные $m-1$ элементов остаются в правой части — partition при этом делает ровно $m-1$ сравнений. Подмассивы по уровням имеют длины $10, 9, 8, \dots, 1$, значит суммарное число сравнений равно $9+8+7+6+5+4+3+2+1+0 = 45$, что в точности совпадает с формулой $\frac{n(n-1)}{2} = \frac{10 \cdot 9}{2} = 45$.

Пример 2. Сравнение вырожденного случая со сбалансированным на том же $n$. Для того же $n=10$ оценка числа сравнений при идеально сбалансированном разбиении на каждом шаге составляет примерно $n \log_2 n = 10 \cdot \log_2 10 \approx 10 \cdot 3{,}32 \approx 33{,}2$. Соотношение с вырожденным случаем: $45 / 33{,}2 \approx 1{,}35$ — на $n=10$ разница ещё не выглядит драматичной. Но при $n=1000$ вырожденный случай даёт $\frac{1000\cdot999}{2} \approx 499\,500$ сравнений, тогда как сбалансированный — $1000 \cdot \log_2 1000 \approx 1000 \cdot 9{,}97 \approx 9\,970$ — разрыв вырастает уже примерно в $50$ раз, и продолжает расти дальше линейно с $n$, поскольку один сценарий растёт квадратично, а другой — почти линейно.

Пример 3. Как случайный выбор pivot спасает именно на «вредных» данных. Возьмём тот же отсортированный массив $[1, 2, \dots, 10]$, но теперь на каждом уровне рекурсии pivot выбирается случайным образом среди элементов текущего подмассива, а не всегда как первый или последний элемент. Допустим, на первом уровне случайно выбран элемент со значением $5$ (пятый по счёту в исходном массиве). Тогда partition разделит массив на $[1,2,3,4]$ (то, что $<5$) и $[6,7,8,9,10]$ (то, что $>5$) — разбиение $4$ на $5$, почти пополам, несмотря на то что исходные данные были максимально «враждебны» для детерминированной стратегии «первый элемент». Рекурсия продолжится на этих двух примерно равных половинах, и с высокой вероятностью останется примерно сбалансированной и дальше — ведь вероятность выбрать наименьший или наибольший элемент подмассива размера $m$ равна лишь $2/m$, а не гарантирована, как при фиксированной стратегии «первый». Именно в этом суть: у детерминированного алгоритма худший случай — это свойство конкретных входных данных, а у рандомизированного — крайне маловероятное (хотя формально не невозможное) стечение случайных решений внутри самого алгоритма, которое не может систематически повторяться на одном и том же входе при повторных запусках.

Почему это важно

На практике массивы очень часто оказываются не случайно перемешанными, а закономерно устроенными: временные ряды, идентификаторы записей, логи событий — всё это регулярно приходит уже частично или полностью отсортированным, обратно отсортированным, либо составленным из небольшого числа отсортированных блоков (что типично для повторной сортировки почти неизменившихся данных). Алгоритм, использующий детерминированную стратегию «первый» или «последний элемент» как pivot, систематически проваливается именно на таких — не редких, а, наоборот, весьма распространённых в реальных системах — входных данных. Именно поэтому качественные библиотечные реализации либо используют истинно случайный (или псевдослучайный, непредсказуемый для внешнего наблюдателя) выбор pivot, либо комбинацию медианы трёх с ограничением глубины рекурсии, при превышении которой алгоритм переключается на другой метод сортировки с гарантированным $O(n \log n)$ в худшем случае (такая гибридная схема называется introsort и используется, например, во многих реализациях std::sort в C++).

Сортировка на месте и её неустойчивость

Интуиция

«Сортировка на месте» (in-place) означает, что алгоритм переставляет элементы прямо внутри исходного массива, не создавая для этого вспомогательную структуру размера $O(n)$. У быстрой сортировки в её in-place реализации (со схемой Ломуто или Хоара) единственные дополнительные затраты памяти — это стек вызовов рекурсии, глубина которого в среднем случае составляет $O(\log n)$, а в худшем — вплоть до $O(n)$ без специальных оптимизаций. Это принципиально отличает её, например, от сортировки слиянием, которая явно выделяет вспомогательный массив размера $O(n)$ для операции слияния на каждом уровне рекурсии — тема следующего урока.

Второе свойство, о котором часто забывают, — неустойчивость. Устойчивая (stable) сортировка гарантирует, что относительный порядок двух элементов с одинаковым ключом сортировки сохраняется таким же, каким он был во входных данных. Быстрая сортировка в её стандартной in-place реализации этой гарантии не даёт: partition, перемещая элементы через дальние свопы (а не через последовательные сдвиги, как в сортировке вставками), может поменять местами два элемента с одинаковым ключом, даже если сам по себе такой обмен не требуется для корректности итогового порядка по ключу.

Определение

Сортировка называется устойчивой (stable), если для любых двух элементов $x$ и $y$ с равными ключами сортировки, где $x$ стоял раньше $y$ во входном массиве, в отсортированном результате $x$ по-прежнему стоит раньше $y$. Быстрая сортировка в её классической in-place реализации этим свойством, вообще говоря, не обладает.

Примеры с разбором

Пример 1. Сравнение затрат памяти: наивная версия против in-place. Наивная реализация из первого раздела (создающая списки left и right на каждом уровне рекурсии) выделяет новую память под копии элементов на каждом уровне — суммарно по всем уровням сбалансированного дерева рекурсии объём скопированных данных пропорционален $n \log n$, хотя единовременно в памяти находится не более нескольких уровней сразу. In-place версия со схемой Ломуто не копирует элементы вовсе — вся дополнительная память сводится к переменным цикла $i$, $j$ и стеку вызовов, глубина которого в среднем случае $O(\log n)$. Для массива в сотни миллионов элементов эта разница — между «поместится в доступную оперативную память» и «не поместится» — может быть решающей.

Пример 2. Наглядная демонстрация нарушения устойчивости. Рассмотрим массив пар (ключ, метка) $A = [(2,\text{«A»}), (2,\text{«B»}), (1,\text{«C»}), (2,\text{«D»})]$, который нужно отсортировать по ключу. Если бы сортировка была устойчивой, результат обязан был бы выглядеть как $[(1,\text{«C»}), (2,\text{«A»}), (2,\text{«B»}), (2,\text{«D»})]$ — тройка с ключом $2$ сохраняет исходный порядок A, B, D.

Применим Ломуто-partition, $lo=0$, $hi=3$, $pivot = A[3] = (2,\text{«D»})$, ключ $=2$.

$i=-1$. $j=0$: $(2,\text{A})$, ключ $2\le 2$? да $\to i=0$, своп $A[0]\leftrightarrow A[0]$ (без изменений). $j=1$: $(2,\text{B})$, ключ $2\le 2$? да $\to i=1$, своп $A[1]\leftrightarrow A[1]$ (без изменений, индексы совпали). $j=2$: $(1,\text{C})$, ключ $1\le 2$? да $\to i=2$, своп $A[2]\leftrightarrow A[2]$ (без изменений).

Цикл завершён. Финальный своп: $A[i+1]\leftrightarrow A[hi]$, то есть $A[3]\leftrightarrow A[3]$ — без изменений, поскольку $i+1=3=hi$.

Массив после этого partition остался неизменным: $[(2,\text{A}), (2,\text{B}), (1,\text{C}), (2,\text{D})]$, pivot встал на индекс $3$. Но подмассив $[0..2] = [(2,\text{A}),(2,\text{B}),(1,\text{C})]$ сам по себе ещё не отсортирован — в нём элемент с ключом $1$ должен оказаться первым. Рекурсивно применим partition к нему: $lo=0$, $hi=2$, $pivot=A[2]=(1,\text{C})$, ключ $=1$.

$i=-1$. $j=0$: $(2,\text{A})$, ключ $2\le 1$? нет. $j=1$: $(2,\text{B})$, ключ $2\le 1$? нет.

Цикл завершён без единого свопа внутри него. Финальный своп: $A[i+1]\leftrightarrow A[hi]$, то есть $A[0]\leftrightarrow A[2]$: элементы $(2,\text{A})$ и $(1,\text{C})$ меняются местами — подмассив становится $[(1,\text{C}), (2,\text{B}), (2,\text{A})]$.

Общий массив на этом этапе: $[(1,\text{C}), (2,\text{B}), (2,\text{A}), (2,\text{D})]$. Оставшийся подмассив $[1..2] = [(2,\text{B}),(2,\text{A})]$ дальнейшим partition (с pivot $=A[2]=(2,\text{A})$) уже не меняется, поскольку оба элемента удовлетворяют условию $\le$ pivot тривиально по индексам. Итоговый результат: $[(1,\text{C}), (2,\text{B}), (2,\text{A}), (2,\text{D})]$.

Сравни с ожидаемым устойчивым результатом $[(1,\text{C}), (2,\text{A}), (2,\text{B}), (2,\text{D})]$: элементы A и B поменялись местами относительно исходного порядка! Это прямая демонстрация неустойчивости — среди элементов с одинаковым ключом их взаимный порядок изменился, хотя сам по себе результат совершенно корректно отсортирован по ключу.

Пример 3. Практическое следствие для многоключевой сортировки. Частый приём при работе с таблицами данных — отсортировать сначала по вторичному ключу, а затем стабильно пересортировать по первичному, полагаясь на то, что стабильная сортировка не разрушит порядок, заданный первым проходом (в результате внутри каждой группы по первичному ключу сохраняется порядок по вторичному). Этот приём работает только с устойчивым алгоритмом сортировки. Если вместо него на втором проходе использовать быструю сортировку, результат первого прохода (порядок по вторичному ключу) может оказаться перемешан внутри групп с одинаковым первичным ключом — ровно так, как элементы A и B поменялись местами в примере 2. Корректная альтернатива — либо сразу сортировать по составному ключу (кортежу «первичный, вторичный»), либо использовать заведомо устойчивый алгоритм, например сортировку слиянием или её практичный гибрид Timsort, которым по умолчанию сортируются списки в Python.

Почему это важно

In-place свойство — это выигрыш по памяти, который становится решающим именно тогда, когда данных много: сортировка сотен миллионов записей на сервере с ограниченной оперативной памятью может физически не поместиться, если использовать алгоритм с $O(n)$ дополнительной памяти, тогда как $O(\log n)$-затратная быстрая сортировка справится с тем же объёмом почти без запаса. Неустойчивость, напротив, — это ограничение, о котором легко забыть до тех пор, пока оно не сломает конкретную задачу: если в требованиях явно или неявно заложено «при равных ключах сохранить исходный порядок», использовать стандартную быструю сортировку напрямую нельзя — нужно либо изменить ключ сортировки на составной, либо выбрать заведомо устойчивый алгоритм.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Дан массив $[9, 3, 7, 1, 8]$. Возьми pivot как последний элемент и раздели массив (в наивном, не in-place смысле) на часть «меньше pivot» и часть «больше pivot».

Задание 2. Массив $[4, 4, 4, 4]$ состоит из одинаковых элементов. Почему классическая двухпутевая (Ломуто) partition на таком массиве всё равно может дать сильно несбалансированное разбиение, несмотря на то что все элементы уже «отсортированы» относительно друг друга?

Задание 3. Сколько сравнений выполнит один вызов Ломуто-partition на подмассиве длины $6$?

Задание 4. Обязательно ли опорный элемент (pivot) должен быть медианой сортируемого подмассива?

Задание 5. Массив $[10, 20, 30, 40]$ уже отсортирован по возрастанию. Какая из стратегий — «первый элемент», «последний элемент» или «медиана трёх» (по элементам с индексами $0$, $1$, $3$) — даст самое сбалансированное разбиение на первом же шаге?

Задание 6. Сформулируй базовый случай рекурсии в QuickSort — при каком условии рекурсивный вызов сразу завершается без работы?

Задание 7. Какова асимптотическая сложность по времени одного вызова функции partition для подмассива длины $m$? Обоснуй.

Задание 8. Почему быструю сортировку называют «сортировкой на месте», если она всё же использует память под стек рекурсии?

Задание 9. Дан список пар $[(5,\text{«P»}), (3,\text{«Q»}), (5,\text{«R»})]$. Если бы сортировка по ключу была устойчивой, в каком порядке должны идти элементы с ключом $5$ в результате?

Задание 10. Перечисли четыре стратегии выбора опорного элемента, разобранные в уроке.

Средние (задания 11–20)

Задание 11. Примени Ломуто-partition к массиву $[6, 1, 8, 3, 9, 2]$ с pivot $=$ последний элемент. Дай полную трассировку и итоговый массив.

Задание 12. Для результата предыдущего задания укажи границы двух рекурсивных вызовов QuickSort, которые будут сделаны дальше.

Задание 13. Массив $[15, 22, 8, 3, 41, 6, 19]$ сортируется со случайным выбором pivot; на первом шаге случайно выбран элемент $22$. Оцени (без точной трассировки индексов), насколько сбалансированным получится разбиение.

Задание 14. Оцени высоту дерева рекурсии для массива из $n=1024$ элементов в идеально сбалансированном случае.

Задание 15. Оцени число сравнений в среднем случае для $n=1\,000\,000$, используя приближение $1{,}39 \cdot n \cdot \log_2 n$ (считай $\log_2 1\,000\,000 \approx 19{,}93$).

Задание 16. Массив $[1, 2, \dots, 10]$ уже отсортирован, стратегия pivot $=$ первый элемент. Оцени точное суммарное число сравнений по всем уровням рекурсии.

Задание 17. Сравни результат предыдущего задания ($45$) с оценкой для сбалансированного разбиения $n\log_2 n \approx 33{,}2$ при том же $n=10$. Во сколько раз хуже вырожденный случай?

Задание 18. Дан массив пар $[(2,\text{«A»}), (1,\text{«B»}), (2,\text{«C»}), (2,\text{«D»})]$. Примени один проход Ломуто-partition с pivot $=A[3]=(2,\text{«D»})$. Изменился ли порядок A и C относительно друг друга уже на этом шаге?

Задание 19. В чём сходство и в чём ключевое отличие между partition в QuickSort и построением узла дерева решений в машинном обучении?

Задание 20. Почему in-place свойство QuickSort особенно важно при сортировке данных, которые едва помещаются в оперативную память?

Продвинутые (задания 21–30)

Задание 21. Используя дерево рекурсии, объясни, почему $T(n)=2T(n/2)+O(n)$ даёт именно $O(n \log n)$.

Задание 22. Тем же методом (дерево рекурсии) покажи, что $T(n)=T(n-1)+O(n)$ даёт $O(n^2)$.

Задание 23. Для массива из $n=8$ элементов при рандомизированном QuickSort оцени качественно, насколько вероятно, что pivot окажется экстремумом (минимумом или максимумом) подмассива на всех трёх уровнях рекурсии подряд ($\log_2 8=3$).

Задание 24. Можно ли в принципе сконструировать входной массив, гарантированно вызывающий худший случай для стратегии «медиана трёх (первый, средний, последний)»?

Задание 25. Оцени глубину стека рекурсии для рандомизированного QuickSort на $n=1\,000\,000$ в среднем случае и сравни с абсолютным (практически невозможным) худшим случаем.

Задание 26. Почему правильная инженерная практика — рекурсивно обрабатывать МЕНЬШУЮ из двух частей после partition, а бо́льшую — продолжать в цикле (без нового вложенного вызова)?

Задание 27. Сравни схему Ломуто и схему Хоара по числу свопов на одном partition. Какая обычно эффективнее и почему?

Задание 28. Почему рандомизация pivot настолько полезна в QuickSort, но не имеет смысла как случайный выбор порога разбиения в КАЖДОМ узле дерева решений?

Задание 29. Существует ли перестановка из $6$ попарно различных элементов, для которой рандомизированный QuickSort гарантированно (со $100\%$ вероятностью) отработает за $O(n^2)$? Сравни с гарантией для детерминированной стратегии «первый элемент».

Задание 30. Спроектируй выбор алгоритма сортировки для трёх сценариев: (а) массив из $50$ элементов в горячем цикле, вызываемом миллионы раз в секунду; (б) журнал логов объёмом $200$ ГБ на сервере с $32$ ГБ RAM; (в) список записей, который нужно отсортировать по дате, а затем — без потери первой сортировки — по статусу.

Частые ошибки

❌ Ошибка: Использовать фиксированный выбор pivot (первый или последний элемент) на данных, которые на практике часто оказываются уже отсортированными или почти отсортированными (временные ряды, логи, идентификаторы).

✅ Правильно: Использовать случайный выбор pivot или медиану трёх — детерминированная стратегия «первый/последний элемент» систематически проваливается именно на распространённых в реальных системах данных, а не только в редких искусственных примерах.

💡 Почему: Худший случай $O(n^2)$ для детерминированного pivot — это свойство конкретных входных данных, а не случайность; на отсортированном или почти отсортированном массиве этот худший случай реализуется гарантированно, а не «иногда».

❌ Ошибка: Считать, что быстрая сортировка всегда работает за $O(n \log n)$, потому что «это же QuickSort, он быстрый по определению».

✅ Правильно: $O(n \log n)$ — это оценка среднего случая (или гарантия для рандомизированной версии в математическом ожидании); в худшем случае (при неудачном выборе pivot) сложность деградирует до $O(n^2)$.

💡 Почему: Путаница среднего и худшего случая приводит к ложной уверенности в производительности на новых, ещё не протестированных данных, — особенно опасно в системах, обрабатывающих данные, структура которых заранее не гарантирована случайной.

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

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

💡 Почему: Неустойчивость проявляется не всегда одинаково — на одних данных результат случайно совпадёт с ожидаемым порядком, на других (как показано в разборе partition) относительный порядок равных элементов незаметно нарушится, что трудно диагностировать постфактум.

❌ Ошибка: Путать «на месте» (in-place) с «вообще без дополнительной памяти» и удивляться, обнаружив в реализации стек рекурсии.

✅ Правильно: In-place означает отсутствие копирования самих сортируемых данных в новый массив; небольшая дополнительная память под стек рекурсии ($O(\log n)$ в среднем случае) — это ожидаемая и допустимая часть определения.

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

❌ Ошибка: При разборе Ломуто-partition забывать, что условие сравнения — нестрогое ($\le pivot$, а не $< pivot$), и из-за этого неверно трассировать шаги вручную на массивах с повторяющимися элементами.

✅ Правильно: Элементы, равные pivot, попадают в левую («меньше или равно») зону; при большом числе повторяющихся значений это может серьёзно разбалансировать разбиение, как показано в задании 2 практики.

💡 Почему: Ошибка в трактовке условия сравнения — частая причина неправильной ручной трассировки partition на экзаменах и собеседованиях, а также источник трудноуловимых багов при самостоятельной реализации алгоритма.

❌ Ошибка: Реализовывать рекурсию так, что при любом разбиении сначала вызывается рекурсия для большей части, а для меньшей — тоже отдельным вложенным вызовом, без оптимизации хвостового вызова.

✅ Правильно: Рекурсивно обрабатывать меньшую из двух частей, а бо́льшую — продолжать в цикле той же функции (без нового кадра стека), чтобы гарантировать глубину стека $O(\log n)$ независимо от качества разбиений.

💡 Почему: Без этой оптимизации на достаточно больших и неудачно устроенных данных возможно переполнение стека вызовов (stack overflow) даже там, где сам алгоритм в остальном корректен.

Главное запомнить

✅ Быстрая сортировка следует парадигме «разделяй и властвуй»: выбрать опорный элемент (pivot), разбить подмассив вокруг него, рекурсивно отсортировать обе части — без отдельного шага слияния в конце

✅ Четыре стратегии выбора pivot: первый элемент, последний элемент, случайный элемент, медиана трёх — выбор стратегии не влияет на корректность результата, но принципиально влияет на производительность

✅ Partition — сердце алгоритма: один линейный проход $O(m)$ по подмассиву, физически переставляющий элементы так, чтобы всё $\le pivot$ оказалось левее, а всё $> pivot$ — правее его финальной позиции

✅ Схема Ломуто (один индекс-граница $i$, проход слева направо) проще для понимания; схема Хоара (два встречных указателя) в среднем делает меньше свопов, но не гарантирует финальную позицию pivot ровно на границе

✅ Сбалансированное разбиение даёт рекуррентность $T(n)=2T(n/2)+O(n)$ и сложность $O(n\log n)$; вырожденное разбиение (экстремум как pivot на каждом шаге) даёт $T(n)=T(n-1)+O(n)$ и сложность $O(n^2)$

✅ Худший случай гарантированно реализуется у детерминированного pivot («первый»/«последний» элемент) на уже отсортированных или обратно отсортированных данных — а такие данные регулярно встречаются на практике

✅ Рандомизированный выбор pivot даёт математическое ожидание числа сравнений $O(n\log n)$ для любого фиксированного входа — худший случай там зависит от случайности внутри алгоритма, а не от структуры входных данных

✅ Быстрая сортировка работает на месте (in-place): дополнительная память — только стек рекурсии, $O(\log n)$ в среднем случае, что выгодно отличает её от алгоритмов с $O(n)$ дополнительной памяти

✅ Быстрая сортировка неустойчива (не stable): относительный порядок элементов с равными ключами может измениться — для многоключевой сортировки по этой причине нужен либо составной ключ, либо заведомо устойчивый алгоритм

✅ Идея рекурсивного разбиения данных по выбранному критерию в partition концептуально совпадает со структурой построения узла в дереве решений — оба рекурсивно делят выборку на части, различаясь лишь целью разбиения

Связь с другими темами курса

🔙 Откуда пришли: Из урока 266 — общего обзора алгоритмов сортировки, где быстрая сортировка была представлена схематично, в наивном варианте с копированием списков; этот урок разворачивает её до in-place реализации, полного анализа среднего и худшего случая и практических нюансов.

🔜 Куда идём:

• Сортировка слиянием (урок 268) — прямая противоположность по компромиссам: гарантированный $O(n\log n)$ даже в худшем случае и устойчивость ценой $O(n)$ дополнительной памяти; сравнение двух алгоритмов на одних и тех же данных закрепит понимание, когда какой выбирать
• Пирамидальная сортировка (урок 269) — третий $O(n\log n)$-алгоритм, гарантированно работающий на месте и без деградации до $O(n^2)$, лежащий в основе introsort — гибридной схемы, страхующей QuickSort от худшего случая
• Структуры данных на основе разбиения по порогу (деревья поиска, урок 257) — та же идея «раздели по значению» встречается там в контексте поддержания упорядоченной структуры, а не однократной сортировки массива

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

Интересные факты

📌 Тони Хоар придумал быструю сортировку в 1959–1960 годах в Москве, работая над проектом машинного перевода с русского языка на английский и одновременно учась у Андрея Николаевича Колмогорова — редкий случай, когда фундаментальный алгоритм информатики родился как побочный продукт решения сугубо прикладной лингвистической задачи.

📌 Первая публикация алгоритма в 1961 году в Communications of the ACM состояла из двух отдельных «рецептов» под скромными техническими названиями — «Algorithm 63: Partition» и «Algorithm 64: Quicksort», — без единого намёка на то, что этим алгоритмам предстоит стать одними из самых используемых в истории программирования.

📌 За вклад в информатику, включая разработку языков программирования и формальной семантики (логики Хоара, до сих пор применяемой для доказательства корректности программ), Тони Хоар получил премию Тьюринга в 1980 году — высшую награду в области информатики, эквивалент Нобелевской премии для этой дисциплины.

📌 Многие современные библиотечные реализации сортировки — так называемый introsort, впервые предложенный Дэвидом Массером в 1997 году, — используют QuickSort как основной метод, но отслеживают глубину рекурсии и автоматически переключаются на пирамидальную сортировку, если рекурсия становится подозрительно глубокой (признак приближения к худшему случаю); такая гибридная схема гарантирует $O(n\log n)$ даже в теоретически худшем сценарии, сохраняя типичную для QuickSort скорость на практике.

Лайфхаки и полезные трюки

💡 При ручной трассировке Ломуто-partition удобно держать в голове простое правило: индекс $i$ — это «граница уже подтверждённой левой зоны», а не текущая позиция сравнения; своп на каждом шаге лишь расширяет эту зону на один элемент, если найденный элемент ей подходит.

💡 Если нужно быстро прикинуть, во сколько раз худший случай хуже среднего при данном $n$, используй грубую оценку $\frac{n/2}{\log_2 n}$ — она показывает порядок величины разрыва между квадратичным и квазилинейным ростом без точных вычислений констант.

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

💡 На собеседованиях по алгоритмам вопрос про худший случай QuickSort почти всегда идёт в связке с вопросом «как его избежать» — стоит заранее иметь наготове чёткий ответ про случайный выбор pivot или медиану трёх, а не только формулу сложности.

💡 В своём коде на практике почти никогда не стоит реализовывать QuickSort с нуля вручную — во всех массовых языках есть готовые, тщательно протестированные и оптимизированные реализации (sort() в Python использует Timsort, а не QuickSort, именно из-за требования устойчивости; встроенный qsort в C и многие реализации std::sort в C++ — вариации introsort). Понимание механики нужно не для того, чтобы писать сортировку заново, а для того, чтобы осознанно выбирать между алгоритмами и объяснять их поведение на конкретных данных.

💡 Если стоит выбор между быстрой сортировкой и сортировкой слиянием для конкретной задачи, задай себе два вопроса: важна ли устойчивость (сохранение порядка равных ключей) и насколько жёстко ограничена доступная память? Если да хотя бы на один вопрос — выбирай сортировку слиянием, несмотря на то что быстрая сортировка в среднем случае чуть быстрее по константе.

Быстрая сортировка — редкий пример алгоритма, который одновременно элегантен на бумаге и требует настоящей инженерной аккуратности в реализации: выбор pivot, устройство partition, забота о глубине рекурсии и понимание, когда её неустойчивость сломает задачу, — всё это детали, отделяющие учебный псевдокод от кода, которому можно доверить сортировку продакшен-данных. Ты увидел, как одна и та же идея — рекурсивное разбиение по выбранному критерию — превращается то в сортировку массива, то, чуть раньше в этом уроке, в прообраз построения узла дерева решений, а дальше в курсе прорастёт в разбор альтернативных алгоритмов с другими компромиссами между скоростью, памятью и устойчивостью. Следующий урок — сортировка слиянием — устроен на первый взгляд похоже, но выбирает совершенно другую точку компромисса, и сопоставление этих двух подходов другу с другом закрепит понимание того, что «лучшего» алгоритма сортировки не существует — есть лишь осознанный выбор под конкретную задачу.