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

TL;DR

Быстрая сортировка (quicksort) — рекурсивный алгоритм сортировки по принципу «разделяй и властвуй»: выбирается опорный элемент (pivot), массив разбивается так, что слева оказываются элементы меньше опорного, справа — не меньше, после чего обе части сортируются рекурсивно. Алгоритм сортирует на месте (in-place) и в среднем (и ожидаемо при случайном опорном) работает за [math]\displaystyle{ O(n\log n) }[/math], но в худшем случае — за [math]\displaystyle{ \Theta(n^2) }[/math], если разбиение каждый раз выходит крайне неровным (например, «первый элемент» на уже отсортированном массиве). На практике он очень быстр благодаря хорошей локальности доступа к памяти и малому числу обменов, поэтому лежит в основе std::sort (как introsort) и типичных реализаций qsort. Три ключевых усовершенствования — разбиение Хоара, выбор опорного (случайный/медиана трёх) и трёхпутевое разбиение для дубликатов. Быстрая сортировка неустойчива и требует [math]\displaystyle{ O(\log n) }[/math] памяти на стек рекурсии в среднем ([math]\displaystyle{ O(n) }[/math] в худшем).

Свойство	Значение
Класс	Сортировка сравнением; «разделяй и властвуй»; на месте
Изобретение	Тони Хоар (C. A. R. Hoare), разработан в 1960, опубликован в 1961–1962
Средний случай	[math]\displaystyle{ O(n\log n) }[/math] сравнений
Худший случай	[math]\displaystyle{ \Theta(n^2) }[/math] сравнений
Лучший случай	[math]\displaystyle{ O(n\log n) }[/math]
Память	[math]\displaystyle{ O(\log n) }[/math] под стек в среднем, [math]\displaystyle{ O(n) }[/math] в худшем (in-place по данным)
Устойчивость	нет (меняет порядок равных)
Локальность	высокая (последовательные проходы по массиву)
Улучшения	случайный опорный, медиана трёх, трёхпутевое разбиение, переключение на heapsort (introsort)
Родственники	Сортировки (план): слиянием, пирамидальная (Двоичная куча)
Где встречается	std::sort, qsort, Arrays.sort (primitives), quickselect

Определения

Быстрая сортировка (quicksort) — алгоритм сортировки массива [math]\displaystyle{ a[lo..hi] }[/math], состоящий из трёх шагов:

1. выбрать опорный элемент (pivot) на отрезке;
2. разбить (partition) отрезок на две части так, чтобы ни один элемент левой части не был больше элемента правой; для Ломуто это даёт [math]\displaystyle{ a[lo..p-1] \lt a[p] \le a[p+1..hi] }[/math], для Хоара равные могут остаться с обеих сторон;
3. рекурсивно отсортировать части по границам, которые вернула схема разбиения (для Ломуто — [math]\displaystyle{ a[lo..p-1] }[/math] и [math]\displaystyle{ a[p+1..hi] }[/math]).

Конкретная схема разбиения задаёт границы рекурсии. Ломуто возвращает индекс опорного p: рекурсия идёт по a[lo..p−1] и a[p+1..hi]. Хоар возвращает границу j: рекурсия идёт по a[lo..j] и a[j+1..hi]; опорный может остаться внутри левой части и не обязан стоять на итоговом месте.

Опорный элемент (pivot) — значение, относительно которого делится отрезок. От его выбора зависит баланс частей, а значит — и сложность.

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

In-place (на месте) — алгоритм переставляет элементы внутри исходного массива, используя [math]\displaystyle{ O(1) }[/math] (или [math]\displaystyle{ O(\log n) }[/math] под рекурсию) дополнительной памяти, в отличие от сортировки слиянием с её буфером [math]\displaystyle{ O(n) }[/math].

Устойчивость (stability) — сохранение взаимного порядка равных элементов. Быстрая сортировка неустойчива: обмены могут поменять местами равные ключи.

Рекуррентность. Если разбиение даёт части размеров [math]\displaystyle{ k }[/math] и [math]\displaystyle{ n-1-k }[/math], стоимость [math]\displaystyle{ T(n) = T(k) + T(n-1-k) + \Theta(n) }[/math], где [math]\displaystyle{ \Theta(n) }[/math] — одно разбиение.

Рандомизация. Выбор опорного случайно из отрезка делает время ожидаемым [math]\displaystyle{ O(n\log n) }[/math] при любом входе (вероятностная гарантия против «заговора» данных).

Обозначения. [math]\displaystyle{ n }[/math] — размер массива; [math]\displaystyle{ lo, hi, p }[/math] — границы и позиция опорного; [math]\displaystyle{ j }[/math] — граница, возвращаемая схемой Хоара; [math]\displaystyle{ k }[/math] — размер левой части в рекуррентности (в задачах выбора — номер искомого элемента); [math]\displaystyle{ d }[/math] — число различных значений в массиве (для трёхпутевого разбиения); [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Сортировка слиянием даёт гарантированное [math]\displaystyle{ O(n\log n) }[/math], но требует [math]\displaystyle{ O(n) }[/math] дополнительной памяти и копирует данные. Пирамидальная сортировка (см. Двоичная куча) работает на месте с гарантией [math]\displaystyle{ O(n\log n) }[/math], но плохо ложится на кэш: обращения к куче прыгают по массиву. Быстрая сортировка ищет третий путь: разбиение на месте, один последовательный проход по памяти — и на реальных данных она часто обгоняет и слияние, и пирамидальную сортировку, несмотря на худший случай [math]\displaystyle{ \Theta(n^2) }[/math].

Идея в одном абзаце: опорный элемент делит задачу пополам. Если каждый раз части выходят примерно равными, глубина рекурсии [math]\displaystyle{ \log n }[/math], а на каждом уровне выполняется [math]\displaystyle{ \Theta(n) }[/math] работы — итого [math]\displaystyle{ \Theta(n\log n) }[/math] (см. рис. 2). Если же опорный постоянно оказывается крайним, одна часть пуста, и дерево вырождается в цепочку глубины [math]\displaystyle{ n }[/math] с работой [math]\displaystyle{ \Theta(n^2) }[/math]. Поэтому вся практика быстрой сортировки — вокруг выбора опорного и случая дубликатов.

Рис. 1. Схема Ломуто: опорный встаёт на своё итоговое место; левая и правая части сортируются рекурсивно.

Рис. 2. Сбалансированное разбиение даёт [math]\displaystyle{ \log n }[/math] уровней по [math]\displaystyle{ \Theta(n) }[/math]; вырожденное — цепочку из [math]\displaystyle{ n }[/math] уровней и [math]\displaystyle{ \Theta(n^2) }[/math].

Устройство

Разбиение — ядро алгоритма. Схема Ломуто (см. рис. 3) выбирает опорным последний элемент a[hi] и ведёт указатель j вдоль отрезка, поддерживая указатель i как границу группы «меньше опорного». В конце опорный меняется местами с a[i+1] и встаёт на своё место. Схема Хоара (см. рис. 4) идёт двумя указателями навстречу, обменивая пары «слишком большой слева» и «слишком маленький справа»; она делает меньше обменов и ровнее делит массив с дубликатами.

Рис. 3. Ломуто для [math]\displaystyle{ [7,2,5,9,1,8,3] }[/math]: [math]\displaystyle{ j }[/math] идёт слева направо, [math]\displaystyle{ i }[/math] — граница меньших; в конце 3 встаёт на позицию 2.

Опора на локальность. Все обращения идут последовательно по массиву, поэтому процессор эффективно использует кэш; это главная практическая причина популярности quicksort.

Операции и алгоритмы

Операция: разбиение Ломуто

Идея. Держать указатель [math]\displaystyle{ i }[/math] так, чтобы слева от него стояли элементы меньше опорного, а справа (до [math]\displaystyle{ j-1 }[/math]) — не меньше; по завершении поставить опорный между группами.

Пошаговое описание:

1. pivot ← a[hi], i ← lo−1.
2. Для j от lo до hi−1: если a[j] < pivot, то i ← i+1 и обменять a[i], a[j].
3. Обменять a[i+1] и a[hi]; вернуть p ← i+1.

Инвариант. Перед обработкой a[j]: элементы a[lo..i] меньше pivot, элементы a[i+1..j−1] не меньше pivot.

Функция Partition-Lomuto(a, lo, hi)
Вход:  массив a; границы lo ≤ hi
Выход: индекс p опорного; a[lo..p−1] < a[p] ≤ a[p+1..hi]
Инвариант: a[lo..i] < pivot и a[i+1..j−1] ≥ pivot
Сложность: Θ(hi − lo + 1)
Корректность: инвариант сохраняется на каждой итерации; обмен с a[hi] ставит
              опорный между группами «меньше» и «не меньше».

1  pivot ← a[hi]
2  i ← lo − 1
3  for j ← lo to hi − 1
4      if a[j] < pivot
5          i ← i + 1
6          swap(a[i], a[j])
7  swap(a[i + 1], a[hi])
8  return i + 1

Разбор. a = [7,2,5,9,1,8,3], pivot = 3. После обработки всех j слева соберутся 2, 1; обмен с a[2] ставит 3 на позицию 2: [2,1,3,9,7,8,5] (см. рис. 3).

Сложность. [math]\displaystyle{ \Theta(n) }[/math] сравнений, [math]\displaystyle{ O(1) }[/math] дополнительной памяти.

Крайние случаи. Все элементы [math]\displaystyle{ \ge }[/math] опорного — i не двигается, опорный меняется с a[lo]. Все [math]\displaystyle{ \le }[/math] — опорный уходит в конец. На одинаковых элементах Ломуто делит крайне неровно — источник [math]\displaystyle{ \Theta(n^2) }[/math].

Операция: разбиение Хоара

Идея. Двигаться двумя указателями к центру: i пропускает «маленькие» слева, j — «большие» справа; при остановке обоих обменять их; когда указатели сошлись — вернуть j.

Пошаговое описание:

1. pivot ← a[lo + (hi−lo)/2], i ← lo−1, j ← hi+1.
2. Повторять: i ← i+1, пока a[i] < pivot; j ← j−1, пока a[j] > pivot.
3. Если i ≥ j — вернуть j; иначе обменять a[i], a[j].

Инвариант. Слева от i все элементы [math]\displaystyle{ \le }[/math] pivot-границы, справа от j — все [math]\displaystyle{ \ge }[/math]; после останова [lo..j] и [j+1..hi] непусты и разделены.

Функция Partition-Hoare(a, lo, hi)
Вход:  массив a; границы lo < hi
Выход: граница j; затем рекурсия (lo, j) и (j+1, hi)
Инвариант: слева от i нет элементов > pivot, справа от j нет элементов < pivot
Сложность: Θ(hi − lo + 1)
Корректность: pivot взят из отрезка, поэтому указатели не выходят за границы;
              при i ≥ j части [lo..j] и [j+1..hi] непусты и разделены.

1  pivot ← a[lo + (hi − lo) / 2]        # средний — защита от отсортированного входа
2  i ← lo − 1 ; j ← hi + 1
3  while true
4      repeat i ← i + 1 until a[i] ≥ pivot
5      repeat j ← j − 1 until a[j] ≤ pivot
6      if i ≥ j
7          return j
8      swap(a[i], a[j])

Разбор. a = [5,3,8,4,2,7,1,6], pivot = 4; обмены (5,1) и (8,2) дают [1,3,2,4,8,7,5,6], возврат j = 3 (см. рис. 4). Рекурсия идёт по (lo, j) и (j+1, hi).

Сложность. [math]\displaystyle{ \Theta(n) }[/math] сравнений, меньше обменов, чем у Ломуто.

Крайние случаи. Требуется, чтобы обе возвращённые части были непусты; при равных элементах Хоар с нестрогими сравнениями (≥/≤) делит примерно пополам, а не вырожденно. Опорный не обязан быть на своей позиции.

Рис. 4. Хоар для [math]\displaystyle{ [5,3,8,4,2,7,1,6] }[/math]: указатели сходятся, обменивая пары [math]\displaystyle{ (5,1) }[/math] и [math]\displaystyle{ (8,2) }[/math]; возвращается граница [math]\displaystyle{ j = 3 }[/math].

Операция: рекурсия Quicksort

Идея. Разбить отрезок, зафиксировать границу между частями и рекурсивно отсортировать каждую часть. Схема разбиения задаёт, где проходит граница и что исключается из рекурсии.

Пошаговое описание:

1. Если lo ≥ hi — отрезок пуст или состоит из одного элемента, вернуть управление.
2. Разбить a[lo..hi] выбранной схемой: Partition-Lomuto или Partition-Hoare.
3. Рекурсивно отсортировать левую и правую части по границам, которые вернула схема.
4. (Оптимизация.) Рекурсию вести по меньшей части, а большую обрабатывать циклом — тогда глубина стека [math]\displaystyle{ O(\log n) }[/math].

Инвариант. Отрезок a[lo..hi] содержит те же элементы, что и до вызова. После разбиения все элементы левой части не больше элементов правой; для Ломуто дополнительно a[lo..p−1] < a[p] ≤ a[p+1..hi].

Алгоритм Quicksort-Lomuto(a, lo, hi)
Вход:  массив a; границы lo ≤ hi
Выход: a[lo..hi] отсортирован
Инвариант: a[lo..hi] — перестановка исходных элементов отрезка
Рекуррентность: T(n) = T(k) + T(n−1−k) + Θ(n)
Среднее: Θ(n log n); худшее: Θ(n²)

1  if lo ≥ hi
2      return                              # 0 или 1 элемент
3  p ← Partition-Lomuto(a, lo, hi)
4  Quicksort-Lomuto(a, lo, p − 1)
5  Quicksort-Lomuto(a, p + 1, hi)

Сложность: Θ(n log n) в среднем, Θ(n²) в худшем; память O(log n) под стек.
Корректность: индукция по длине отрезка; разбиение ставит опорный на итоговое
              место, части сортируются по индукции.

Алгоритм Quicksort-Hoare(a, lo, hi)
Вход:  массив a; границы lo ≤ hi
Выход: a[lo..hi] отсортирован
Инвариант: a[lo..hi] — перестановка исходных элементов отрезка
Рекуррентность: T(n) = T(k) + T(n−1−k) + Θ(n)
Среднее: Θ(n log n); худшее: Θ(n²)
1  if lo ≥ hi
2      return
3  j ← Partition-Hoare(a, lo, hi)
4  Quicksort-Hoare(a, lo, j)
5  Quicksort-Hoare(a, j + 1, hi)

Сложность: Θ(n log n) в среднем, Θ(n²) в худшем; память O(log n) под стек.
Корректность: индукция по длине отрезка; Partition-Hoare возвращает границу j так,
              что части (lo..j) и (j+1..hi) непусты и разделены.

Схемы не взаимозаменяемы. Обратите внимание: Хоар возвращает j, поэтому левая часть — a[lo..j], а не a[lo..p−1]. Смешение схем — типичная ошибка.

Разбор. Продолжим пример: [7,2,5,9,1,8,3] после первого разбиения даёт [2,1,3,9,7,8,5]. Левая часть [2,1] при pivot = 1 становится [1,2]; правая [9,7,8,5] рекурсивно делится до [5,7,8,9]. Итог — [1,2,3,5,7,8,9].

Сложность. [math]\displaystyle{ T(n) = T(k) + T(n-1-k) + \Theta(n) }[/math]. При сбалансированном разбиении [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n) }[/math]; при крайнем — [math]\displaystyle{ T(n) = T(n-1) + \Theta(n) = \Theta(n^2) }[/math]. Память — [math]\displaystyle{ O(\log n) }[/math] при рекурсии по меньшей части.

Крайние случаи. [math]\displaystyle{ n = 0 }[/math] и [math]\displaystyle{ n = 1 }[/math] — немедленный возврат. Все элементы равны: Ломуто даёт худший случай [math]\displaystyle{ \Theta(n^2) }[/math], трёхпутевое разбиение — один линейный проход. Отсортированный вход при крайнем опорном — [math]\displaystyle{ \Theta(n^2) }[/math]. Без хвостовой оптимизации глубина стека может достичь [math]\displaystyle{ n }[/math].

Операция: трёхпутевое разбиение (для дубликатов)

Идея. Делить на три группы: < pivot, = pivot, > pivot (Dutch national flag). Группа равных встаёт на место сразу и в рекурсию не идёт (см. рис. 5).

Пошаговое описание:

1. Выбрать pivot (например, средний элемент отрезка).
2. lt ← lo, gt ← hi, i ← lo.
3. Пока i ≤ gt: если a[i] < pivot — обменять a[lt] и a[i], затем lt ← lt+1, i ← i+1; если a[i] > pivot — обменять a[i] и a[gt], затем gt ← gt−1 (без шага i); иначе i ← i+1.
4. Рекурсия по [lo, lt−1] и [gt+1, hi].

Инвариант. a[lo..lt−1] < pivot, a[lt..i−1] = pivot, a[i..gt] не обработано, a[gt+1..hi] > pivot.

Алгоритм Quicksort-3way(a, lo, hi)
Вход:  массив a; границы lo ≤ hi
Выход: a[lo..hi] отсортирован
Инвариант: a[lo..lt−1] < pivot, a[lt..i−1] = pivot, a[i..gt] не обработано, a[gt+1..hi] > pivot
1  if lo ≥ hi: return
2  pivot ← a[lo + (hi − lo) / 2]
3  lt ← lo ; gt ← hi ; i ← lo
4  while i ≤ gt
5      if a[i] < pivot:      swap(a[lt], a[i]); lt ← lt + 1; i ← i + 1
6      else if a[i] > pivot: swap(a[i], a[gt]); gt ← gt − 1
7      else:                 i ← i + 1
8  Quicksort-3way(a, lo, lt − 1)
9  Quicksort-3way(a, gt + 1, hi)

Сложность: Θ(n log n) ожидаемо; при d различных значениях — O(nd) в худшем;
            при d = n это O(n²).
Корректность: инвариант Dutch flag; после цикла [lt..gt] — равные, они исключены
              из рекурсии; рекурсия идёт по строго меньшим отрезкам.

Разбор. [3,1,2,3,3,4,3,2] при pivot 3 даёт <: 1,2,2; =: 3,3,3,3; >: 4 (см. рис. 5). Никакого [math]\displaystyle{ \Theta(n^2) }[/math] на одинаковых ключах.

Сложность. [math]\displaystyle{ \Theta(n\log n) }[/math] ожидаемо; при [math]\displaystyle{ d }[/math] различных значениях — [math]\displaystyle{ O(nd) }[/math] в худшем. При [math]\displaystyle{ d = n }[/math] это [math]\displaystyle{ O(n^2) }[/math]; при малом [math]\displaystyle{ d }[/math] каждый уровень стоит [math]\displaystyle{ O(n) }[/math] сравнений и обменов.

Крайние случаи. Все элементы равны — один проход, рекурсии нет. Равных нет — разбиение сводится к обычному. Пустой или одноэлементный отрезок — немедленный возврат.

Рис. 5. Трёхпутевое разбиение [math]\displaystyle{ [3,1,2,3,3,4,3,2] }[/math]: группы [math]\displaystyle{ \lt 3 }[/math], [math]\displaystyle{ = 3 }[/math] и [math]\displaystyle{ \gt 3 }[/math]; равные исключаются из рекурсии.

Выбор опорного элемента

• первый/последний — [math]\displaystyle{ O(1) }[/math], но вырождается на отсортированных данных;
• случайный — ожидаемое [math]\displaystyle{ O(n\log n) }[/math], прост; стандарт против «заговорённых» тестов;
• медиана трёх — a[lo], a[mid], a[hi]: [math]\displaystyle{ O(1) }[/math], отлично на почти отсортированных;
• медиана медиан (BFPRT) — гарантированный [math]\displaystyle{ O(n) }[/math]-выбор опорного, даёт худшее [math]\displaystyle{ O(n\log n) }[/math], но с большой константой (см. рис. 6).

Рис. 6. Стратегии выбора опорного: первый/последний, случайный, медиана трёх, медиана медиан — от дешёвой к гарантированной.

Сводная таблица сложности

Операция	Лучший	Средний	Худший	Память
Partition (Ломуто или Хоар)	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Quicksort (случайный опорный)	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n\log n) }[/math] ожидаемо	[math]\displaystyle{ \Theta(n^2) }[/math] (крайне редко)	[math]\displaystyle{ O(\log n) }[/math] стек
Quicksort (медиана трёх)	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(\log n) }[/math]
Quicksort с медианой медиан	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]
Quicksort-3way	[math]\displaystyle{ \Theta(n) }[/math] (все равны)	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ O(nd) }[/math]	[math]\displaystyle{ O(\log n) }[/math]
Quickselect ([math]\displaystyle{ k }[/math]-й элемент)	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math] ожидаемо	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]

Здесь [math]\displaystyle{ d }[/math] — число различных значений в массиве (см. «Обозначения»). Для Quicksort-3way [math]\displaystyle{ O(nd) }[/math] при [math]\displaystyle{ d = n }[/math] превращается в [math]\displaystyle{ O(n^2) }[/math]; при малом [math]\displaystyle{ d }[/math] каждый уровень стоит [math]\displaystyle{ O(n) }[/math].

Память Quickselect указана для in-place варианта: он перемешивает входной массив, поэтому в листинге принимает ссылку (std::vector<int>&) и не копирует данные.

Оговорка: «средний» для быстрой сортировки — это ожидание по случайному опорному (или по случайным входам). Худший случай [math]\displaystyle{ \Theta(n^2) }[/math] достижим на специально подобранных входах, если опорный выбирается детерминированно; медиана трёх на практике делает его крайне редким.

Трассировка примера

a = [7, 2, 5, 9, 1, 8, 3], разбиение Ломуто, pivot = 3.

Шаг	j	Действие	Массив
старт	—	i = −1, pivot = 3	7 2 5 9 1 8 3
1	0	a[0]=7 ≥ 3 — пропуск	7 2 5 9 1 8 3
2	1	a[1]=2 < 3 → i=0, swap	2 7 5 9 1 8 3
3	2	a[2]=5 ≥ 3 — пропуск	2 7 5 9 1 8 3
4	3	a[3]=9 ≥ 3 — пропуск	2 7 5 9 1 8 3
5	4	a[4]=1 < 3 → i=1, swap	2 1 5 9 7 8 3
6	5	a[5]=8 ≥ 3 — пропуск	2 1 5 9 7 8 3
итог	—	swap(a[2], a[6]), p = 2	2 1 3 9 7 8 5

Далее рекурсия: Quicksort([2,1]) и Quicksort([9,7,8,5]). Левая часть при pivot = 1 переставит 2 и 1; правая продолжит делиться. Полный массив отсортируется в [1,2,3,5,7,8,9]. Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Корректность разбиения

Утверждение (Ломуто). После Partition-Lomuto(a, lo, hi) выполняется [math]\displaystyle{ a[lo..p-1] \lt a[p] \le a[p+1..hi] }[/math], где [math]\displaystyle{ p }[/math] — возвращённый индекс.

Доказательство. Инвариант цикла: перед итерацией j элементы a[lo..i] меньше pivot, а a[i+1..j-1] не меньше pivot. При a[j] < pivot увеличиваем i и обмениваем a[i] с a[j], восстанавливая инвариант; иначе a[j] уже в «правой» группе. По завершении i+1 — первая позиция правой группы; обмен с a[hi] (значение pivot) ставит pivot точно между группами. Значит, слева — строго меньше, справа — не меньше. [math]\displaystyle{ \square }[/math]

Корректность Quicksort

Индукция по длине отрезка. База: 0 или 1 элемент отсортированы. Шаг: разбиение делит элементы на две части так, что каждый элемент левой не больше каждого элемента правой; по индукции обе части сортируются рекурсивно; вместе они дают полностью отсортированный отрезок. [math]\displaystyle{ \square }[/math]

Оценка времени

Одно разбиение стоит [math]\displaystyle{ \Theta(n) }[/math], рекуррентность:

[math]\displaystyle{ T(n) = T(k) + T(n-1-k) + \Theta(n). }[/math]

• Худший случай [math]\displaystyle{ k = 0 }[/math] (или [math]\displaystyle{ k = n-1 }[/math]): [math]\displaystyle{ T(n) = T(n-1) + \Theta(n) = \Theta(n^2) }[/math].
• Лучший/сбалансированный [math]\displaystyle{ k \approx n/2 }[/math]: [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n) }[/math] (master theorem, случай 2, см. Асимптотическая сложность (план)).
• Средний/ожидаемый. При случайном опорном ожидаемое число сравнений — [math]\displaystyle{ 2n\ln n \approx 1.39\,n\log_2 n = \Theta(n\log n) }[/math]; дерево рекурсии имеет ожидаемую глубину [math]\displaystyle{ O(\log n) }[/math].

Глубина стека. Рекурсия по меньшей части ограничивает глубину [math]\displaystyle{ O(\log n) }[/math]; иначе в худшем случае возможна глубина [math]\displaystyle{ n }[/math] и переполнение стека.

Худший случай и защита

Худший случай достигается, когда опорный каждый раз крайний: отсортированный массив при опорном «последний/первый», или специально подобранные «анти-quicksort» входы. Защита: случайный опорный (ожидание), медиана трёх (практика), introsort (переключение на heapsort при глубине [math]\displaystyle{ 2\log n }[/math]), медиана медиан (гарантия).

Сравнение с альтернативами

Алгоритм	Средний	Худший	Память	Устойчив	Особенность
Быстрая (quicksort)	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	на месте, кэш-дружелюбна
Слиянием (mergesort)	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	предсказуемое время
Пирамидальная (heapsort)	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет	гарантия, хуже кэш
Introsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	quicksort + heapsort при глубине
Timsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	адаптивна, [math]\displaystyle{ O(n) }[/math] на почти отсортированных

Сводка — на рис. 7.

Рис. 7. Quicksort против mergesort, heapsort, introsort и Timsort: средняя скорость и память против гарантий и устойчивости.

Вердикт. Нужна максимальная средняя скорость на месте — берут быструю сортировку (introsort). Нужна устойчивость или гарантия без риска — слиянием/Timsort. Нужна гарантия при [math]\displaystyle{ O(1) }[/math] памяти — пирамидальная. Для «[math]\displaystyle{ k }[/math]-го элемента» без полной сортировки — quickselect.

Где применяется

1. Стандартные библиотеки. std::sort в C++ реализован как introsort (quicksort + переключение на heapsort при глубокой рекурсии + сортировка вставками на малых отрезках) [1][8]; qsort в C обычно реализуется quicksort-подобным алгоритмом, но стандарт C алгоритм не фиксирует [4]. Почему: лучшая средняя скорость и локальность на практике.

1. Java. Arrays.sort для примитивов использует dual-pivot quicksort (два опорных, Ярославский, 2009), для объектов — Timsort (устойчивость важна). Почему: примитивы сравниваются дёшево, устойчивость не нужна [6].

1. Выбор [math]\displaystyle{ k }[/math]-го элемента (quickselect). Тот же механизм разбиения даёт [math]\displaystyle{ k }[/math]-й по порядку элемент за [math]\displaystyle{ O(n) }[/math] в среднем, без полной сортировки: медианы, перцентили, «топ-[math]\displaystyle{ k }[/math]» [5].

1. Системы с большими массивами. Сортировка больших числовых массивов (научные вычисления, аналитика) — quicksort из-за кэш-дружелюбности и in-place характера [7].

1. Внешняя сортировка (дисковые данные). На дисках чаще берут mergesort из-за устойчивости и последовательного чтения, но in-memory фаза нередко использует quicksort [7].

Историческая справка

Быструю сортировку изобрёл Чарльз Энтони Ричард Хоар (C. A. R. Hoare). Алгоритм появился в 1960 году (реализация на Algol, при поддержке проекта автоматического перевода «Алгол-60»), а публикация Quicksort вышла в The Computer Journal в 1962 году [2]. Исходная схема — разбиение двумя указателями (схема Хоара). В 1961 году Хоар также описал «FIND» — алгоритм выбора [math]\displaystyle{ k }[/math]-го элемента, положивший начало quickselect.

Роберт Седжвик в серии работ 1970-х годов (диссертация 1975; статья Implementing Quicksort Programs, 1978) провёл тонкий вероятностный анализ и ввёл практические улучшения: медиану трёх, сортировку вставками на малых отрезках, рекурсию по меньшей части [3][5]. Бентли и МакИлрой в статье Engineering a Sort Function (1993) детально разобрали трёхпутевое разбиение и инженерные приёмы, ставшие основой библиотечных реализаций [4]. Мюссер в 1997 году предложил introsort — гибрид, гарантирующий [math]\displaystyle{ O(n\log n) }[/math] в худшем случае [1]. Владимир Ярославский в 2009 году предложил dual-pivot quicksort (Java 7+) [6]; ⚠️ точные выходные данные этой работы не сверены.

Название «quicksort» — от «быстрого» поведения на практике; теоретически [math]\displaystyle{ \Theta(n^2) }[/math] в худшем случае роднит его с сортировкой вставками, но средняя скорость и локальность сделали его одним из самых применяемых алгоритмов.

Типичные ошибки и подводные камни

• Плохой выбор опорного. «Первый/последний» на отсортированных данных даёт [math]\displaystyle{ \Theta(n^2) }[/math]; лечится случайным опорным или медианой трёх.
• Одинаковые ключи. Ломуто (а также схемы, отправляющие все равные в одну часть) вырождается на массиве из равных; спасает трёхпутевое разбиение. Хоар с нестрогими сравнениями ≥/≤ делит равные примерно пополам.
• Переполнение стека. Глубокая рекурсия ([math]\displaystyle{ n }[/math] уровней) валит программу; рекурсируйте по меньшей части или переключайтесь на heapsort (introsort).
• Бесконечная рекурсия в Хоаре. Вызов Quicksort(lo, j) и Quicksort(j+1, hi) требует, чтобы обе части были непусты; при ошибке в границах — зацикливание.
• Переполнение (lo+hi)/2. На больших индексах сумма переполняет int; пишите lo + (hi−lo)/2.
• Ожидание устойчивости. Quicksort неустойчив; для «сортировки по двум ключам с сохранением порядка» берите слиянием/Timsort.
• Рекурсия без base case. if (lo >= hi) return; обязателен, иначе бесконечность/мусор.
• Вызов на пустом/одноэлементном массиве. Должен мгновенно завершаться.
• «Анти-quicksort» на соревнованиях. Детерминированный опорный можно подловить специальными тестами; рандомизация или introsort обязательны.
• Путаница partition-схем. Ломуто возвращает индекс опорного, Хоар — границу (не опорного); смешение ломает обе части.

Задачи для практики

1. Основная реализация. Напишите Quicksort с разбиением Ломуто. Ограничение: [math]\displaystyle{ O(\log n) }[/math] памяти на стек. Подсказка: Partition возвращает индекс опорного.

1. Хоар. Реализуйте разбиение Хоара и покажите, почему его части всегда непусты. Подсказка: исследуйте случай i == j.

1. Ожидаемое время. Докажите, что при случайном опорном ожидаемое число сравнений есть [math]\displaystyle{ \Theta(n\log n) }[/math]. Подсказка: вероятность сравнить [math]\displaystyle{ i }[/math]-й и [math]\displaystyle{ j }[/math]-й элементы.

1. Худший вход. Для «последнего» опорного постройте вход, дающий [math]\displaystyle{ \Theta(n^2) }[/math], и проверьте подсчётом сравнений. Подсказка: отсортированный массив.

1. Дубликаты. Сравните Ломуто, Хоар и трёхпутевое разбиение на массиве из равных элементов. Подсказка: считайте глубину рекурсии.

1. [math]\displaystyle{ k }[/math]-й элемент. Реализуйте quickselect и сравните его время с полной сортировкой при малых [math]\displaystyle{ k }[/math]. Подсказка: рекурсия только в одну сторону.

1. Хвостовая оптимизация. Переделайте Quicksort так, чтобы стек был [math]\displaystyle{ O(\log n) }[/math] даже в худшем случае. Подсказка: рекурсия по меньшей части, цикл по большей.

1. Медиана трёх. Добавьте выбор медианы трёх и измерьте число сравнений на почти отсортированных данных. Подсказка: сравните с «последним».

Связанные темы

• Сортировки — обзор сортировок и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
• Сортировка слиянием, Пирамидальная сортировка, Timsort — альтернативы: устойчивость и гарантия.
• Сортировка вставками — «хвост» introsort на коротких отрезках.
• Двоичная куча — пирамидальная сортировка и очередь с приоритетом.
• Асимптотическая сложность — рекуррентности, master theorem, средний/худший случай.
• Амортизационный анализ — анализ в среднем и ожидаемом (сравнение подходов).
• Дерево отрезков — другой пример «разделяй и властвуй» на массиве.

Источники

1. Musser D. R. Introspective Sorting and Selection Algorithms // Software: Practice and Experience. — 1997. — Vol. 27, № 8 (introsort).
2. Hoare C. A. R. Quicksort // The Computer Journal. — 1962. — Vol. 5, № 1.
3. Sedgewick R. Implementing Quicksort Programs // Communications of the ACM. — 1978. — Vol. 21, № 10.
4. Bentley J. L., McIlroy M. D. Engineering a Sort Function // Software: Practice and Experience. — 1993. — Vol. 23, № 11 (трёхпутевое разбиение).
5. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 7 «Quicksort»; гл. 9 (выбор за линейное время).
6. Wild S., Nebel M. E., Reitzig R., Laube U. Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn // ALENEX. — 2013 (по вторичным источникам) ⚠️ точные выходные данные не сверены.
7. Wikipedia: Quicksort. URL: https://en.wikipedia.org/wiki/Quicksort.
8. cppreference: std::sort. URL: https://en.cppreference.com/w/cpp/algorithm/sort.