Быстрая сортировка (quicksort) — это алгоритм упорядочивания массива по принципу «разделяй и властвуй»: массив делится на две части относительно опорного элемента, части сортируются рекурсивно. Схема Хоара (Hoare partition scheme) — конкретный способ разбиения, предложенный Тони Хоаром в 1960 году, отличный от более распространенной в учебниках схемы Ломуто. Дальше разберем разбиение по шагам на маленьком массиве, приведем рабочий код и сравним быструю сортировку с другими методами.
Содержание
Quicksort, разбиение и опорный элемент — не одно и то же
В статьях про быструю сортировку три термина часто сливают в один, хотя это разные уровни:
- Quicksort — весь алгоритм: выбор опоры, разбиение, рекурсия на двух частях.
- Разбиение (partition) — один шаг: переставить элементы массива так, чтобы слева оказались значения не больше опорного, справа — не меньше.
- Опорный элемент (pivot) — значение, относительно которого идет разбиение на этом шаге.
Схема Ломуто и схема Хоара по-разному переставляют элементы внутри одного и того же шага разбиения, и это дает разный практический результат, о котором ниже. Коротко о разнице: в схеме Ломуто опору обычно берут последним элементом подмассива и одним указателем последовательно передвигают все элементы меньше опоры в начало, а в конце ставят опору на границу — после этого опора гарантированно стоит на своем финальном месте в отсортированном массиве. Схема Хоара работает двумя встречными указателями и делает меньше перестановок в среднем, но, как показано ниже, не гарантирует опоре финальную позицию сразу после одного разбиения.
Пошаговый разбор схемы Хоара на массиве
Возьмем массив [8, 3, 1, 9, 5, 4] и опорный элемент — первый элемент, 8 (в классической схеме Хоара опору берут именно так). Заводим два указателя: i перед началом массива, j после конца.
Шаг 1. i сдвигается вправо, пока не найдет элемент не меньше опоры: A[0]=8 уже не меньше 8, значит i=0. j сдвигается влево, пока не найдет элемент не больше опоры: A[5]=4 подходит, j=5. Так как i<j, меняем местами A[0] и A[5]. Массив: [4, 3, 1, 9, 5, 8].
Шаг 2. i идет дальше от 0: A[1]=3 меньше опоры, A[2]=1 меньше опоры, A[3]=9 не меньше — стоп, i=3. j идет дальше от 5: A[4]=5 не больше опоры — стоп, j=4. Так как i<j, меняем A[3] и A[4]. Массив: [4, 3, 1, 5, 9, 8].
Шаг 3. i от 3: A[4]=9 не меньше опоры — стоп, i=4. j от 4: A[3]=5 не больше опоры — стоп, j=3. Теперь i>=j (4>=3), разбиение закончено, функция возвращает j=3.
Важный нюанс, который часто упрощают неверно: в схеме Хоара опорный элемент не обязан встать на свое финальное место после разбиения. Здесь 8 осталась на индексе 5, а не заняла границу раздела — это упрощение верно для схемы Ломуто, но не для схемы Хоара. Границей раздела служит возвращенный индекс j=3: рекурсия дальше идет по подмассивам [0..3] и [4..5].
Если продолжить рекурсию тем же способом на [4, 3, 1, 5] и на [9, 8], в итоге получится отсортированный массив [1, 3, 4, 5, 8, 9] — можно проверить теми же двумя правилами сдвига указателей на каждом подмассиве.
Код на Python
def hoare_partition(arr, lo, hi):
pivot = arr[lo]
i = lo - 1
j = hi + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quicksort(arr, lo, p)
quicksort(arr, p + 1, hi)
return arr
data = [8, 3, 1, 9, 5, 4]
print(quicksort(data))Вывод в консоли:
[1, 3, 4, 5, 8, 9]
Это тот же результат, что получился при ручном разборе — массив отсортирован по возрастанию. Рекурсия останавливается, когда lo >= hi, то есть подмассив состоит из одного элемента или пуст: такой подмассив уже отсортирован по определению.
Сложность: от чего зависит O(n log n) или O(n^2)
Средняя сложность быстрой сортировки — O(n log n): при более-менее сбалансированном разбиении на каждом уровне рекурсии массив делится примерно пополам, а уровней получается порядка log n.
Худшая сложность — O(n^2). Она возникает, если разбиение раз за разом получается вырожденным — опора оказывается самым маленьким или самым большим элементом подмассива, и одна из двух частей пустая. Это систематически происходит на уже отсортированном или отсортированном в обратном порядке массиве, если опору всегда берут первым или последним элементом — как в примере выше. На практике это лечат случайным выбором опоры или медианой трех элементов (первого, среднего, последнего), что делает вырожденное разбиение маловероятным на реальных данных.
Разберем худший случай на конкретном массиве: [1, 2, 3, 4, 5, 6], уже отсортированном по возрастанию, опора — первый элемент 1. Указатель i сразу останавливается на индексе 0, потому что A[0]=1 не меньше опоры. Указатель j идет от конца массива влево и останавливается только на индексе 0, потому что все элементы от 2 до 6 больше опоры. В итоге i и j совпадают на первом же шаге, разбиение возвращает j=0 без единой перестановки, и подмассивы получаются размером 1 и 5 — максимально несбалансированно. Если такое повторяется на каждом уровне рекурсии, глубина рекурсии становится n, а не log n, и общее время работы деградирует до O(n^2).
Память — в среднем O(log n) на стек рекурсивных вызовов, в худшем случае (без ограничения глубины) — O(n). Поэтому промышленные реализации, включая std::sort в C++ и сортировку в стандартной библиотеке многих языков, на практике используют не чистый quicksort, а гибрид (интросорт): при слишком глубокой рекурсии алгоритм переключается на heapsort, чтобы гарантировать O(n log n) в худшем случае.
Быстрая сортировка по схеме Хоара — неустойчивая: она не гарантирует, что элементы с одинаковым ключом сохранят взаимный порядок после сортировки, потому что переставляет их через сравнение с опорой, а не подряд.
Сравнение с другими способами сортировки
| Метод | Средняя сложность | Худшая сложность | Доп. память | Устойчивость | Когда применять |
|---|---|---|---|---|---|
| Быстрая (Хоара) | O(n log n) | O(n^2) | O(log n) | нет | сортировка в памяти общего назначения |
| Пузырьковая | O(n^2) | O(n^2) | O(1) | да | только обучение алгоритмам |
| Шейкерная (коктейльная) | O(n^2) | O(n^2) | O(1) | да | маленький почти отсортированный массив |
| Расческа | строго не выведена* | O(n^2) | O(1) | нет | простая альтернатива пузырьковой |
| Вставками | O(n^2) | O(n^2) | O(1) | да | маленькие массивы, почти отсортированные данные |
| Пирамидальная (heapsort) | O(n log n) | O(n log n) | O(1) | нет | нужна гарантия без всплеска памяти |
| Блочная (bucket sort) | O(n + k) | O(n^2) | O(n + k) | зависит от внутренней сортировки | данные равномерно распределены по диапазону |
Несколько уточнений к таблице. Расческа (comb sort) сравнивает не соседние, а удаленные друг от друга элементы, постепенно сокращая разрыв — обычно с коэффициентом сокращения около 1.3 на каждом проходе, это устраняет проблему «черепах» пузырьковой сортировки (маленьких значений в конце массива). *Про сложность расчески часто путают лучший и средний случай: доказанная оценка O(n log n) относится к лучшему случаю (почти отсортированный массив), а для среднего строгого результата нет — известна только более слабая оценка Ω(n^2/2^p), где p — число проходов с уменьшающимся разрывом; на случайных данных с коэффициентом 1.3 расческа на практике ведет себя близко к n log n, но это наблюдение, а не доказанная граница. Пирамидальная сортировка сначала строит из массива бинарную кучу, а затем поочередно извлекает максимум и ставит его в конец — это не то же самое, что просто искать максимум линейным проходом и переставлять его: построение кучи и есть источник гарантии O(n log n). Блочная сортировка быстро деградирует до O(n^2), если данные распределены неравномерно и почти все элементы попадают в одну корзину.
Выводы
- Быстрая сортировка (quicksort) — это алгоритм целиком, разбиение (partition) — один его шаг, а схема Хоара — конкретный способ выполнить этот шаг, отличный от схемы Ломуто.
- В схеме Хоара опорный элемент после разбиения не обязательно занимает свое финальное место в массиве — на подмассивы делит именно возвращенный индекс.
- Средняя сложность быстрой сортировки O(n log n), худшая O(n^2) — худший случай типичен для уже отсортированных данных при наивном выборе опоры (первый или последний элемент).
- Быстрая сортировка неустойчива и в худшем случае требует O(n) памяти на стек рекурсии, поэтому промышленные библиотеки используют гибрид с heapsort.
- Для маленьких или почти отсортированных массивов практичнее сортировка вставками, для гарантии без риска O(n^2) — пирамидальная сортировка.
Где применяется / связь с практикой
Освойте тему на практике
Разбор партиций, рекурсии и оценки сложности алгоритмов — база курса Алгоритмы и структуры данных в Otus: там разбирают не только сортировки, но и то, как выбирать структуру данных и оценивать алгоритм по времени и памяти под конкретную задачу.
Освойте тему на практике
Если пока не уверены, что тема подходит именно вам, можно начать с открытых уроков Otus по алгоритмам и структурам данных — расписание открытых уроков.
FAQ
Почему быструю сортировку иногда называют qsort?
Это историческое имя функции быстрой сортировки в стандартной библиотеке языка C, которое закрепилось как разговорный синоним алгоритма, хотя конкретная реализация внутри qsort зависит от компилятора.
Можно ли сделать быструю сортировку устойчивой?
Формально да, если хранить рядом с каждым элементом его исходный индекс и сравнивать по паре (значение, индекс) при равенстве ключей, но это увеличивает память и почти всегда проще взять устойчивый алгоритм вроде сортировки вставками или timsort.
Что произойдет, если в массиве все элементы одинаковые?
При наивном выборе опоры (первый или последний элемент) без специальной обработки равных значений это тоже вырожденный случай, близкий к худшему по времени; классическая схема Хоара переносит такие элементы в обе части почти поровну, что на практике ведет себя лучше, чем на отсортированном массиве, но по-прежнему требует случайного или медианного выбора опоры как общей защиты.
