Быстрая сортировка (алгоритм)¶
Быстрая сортировка (quick sort) — алгоритм сортировки, основанный на принципе «разделяй и властвуй». Средняя асимптотическая сложность алгоритма составляет O(n log n), при этом в худшем случае она деградирует до O(n²). Быстрая сортировка была разработана в 1959 году британским учёным Чарльзом Хоаром, работавшим тогда в Массачусетском технологическом институте.
¶Принцип работы
Алгоритм состоит из трёх шагов:
- Выбор опорного элемента (pivot) из массива.
- Разделение (partition): массив перестраивается так, что все элементы, меньшие опорного, оказываются слева от него, а все большие — справа. После этого опорный элемент занимает своё финальное положение в отсортированном массиве.
- Рекурсивное применение алгоритма к подмассивам слева и справа от опорного элемента.
Базис рекурсии — подмассив длиной 0 или 1, который считается отсортированным.
Пример разделения массива [3, 6, 8, 10, 1, 2, 1] с опорным элементом 1 (последний): после прохода массив преобразуется в [1, 1, 8, 10, 3, 6, 2], где все элементы слева от первого 1 не больше него, а справа — больше. Затем рекурсия применяется к левому и правому подмассивам.
¶Выбор опорного элемента
Стратегия выбора опорного элемента существенно влияет на производительность:
- Последний или первый элемент массива — простейший вариант, но на уже почти отсортированных данных приводит к худшей сложности O(n²).
- Случайный элемент — выбор случайного опорного элемента даёт хорошее среднее поведение на любых данных.
- Медиана трёх (median-of-three) — берётся медиана из первого, среднего и последнего элементов; популярный компромисс между простотой и устойчивостью.
- Медиана медиан (алгоритм Бладера — Хоара) — выбор опорного элемента за линейное время гарантирует сбалансированное разделение и худшую сложность O(n log n), однако на практике применяется редко из-за больших констант.
¶Схемы разделения
Существует несколько способов реализации шага partition:
- Схема Хоара (1961): два указателя движутся навстречу друг другу с обоих концов подмассива; элементы меняются местами, когда левый указатель стоит на элементе больше опорного, а правый — на элементе меньше. Считается более эффективной, чем схема Ломуто, и требует в среднем примерно втрое меньше обменов.
- Схема Ломуто: один проход слева направо; элементы меньше опорного накапливаются в начале массива. Более простая в реализации, но производит больше обменов.
- Трёхпутевое разделение (three-way partition, Dijkstra): массив разбивается на три части — «меньше опорного», «равно опорному», «больше опорного». Особенно эффективно при наличии большого числа повторяющихся ключей.
¶Худший и лучший случаи
Худший случай (O(n²)) возникает, когда разделение каждый раз даёт крайне несбалансированные подмассивы — например, при выборе наименьшего или наибольшего элемента в качестве опорного на уже отсортированном массиве. Лучший случай (O(n log n)) достигается при идеально сбалансированных разделениях.
Для защиты от худшего случая на практике применяют:
- случайный выбор опорного элемента;
- гибридную стратегию: при малом размере подмассива (обычно 8–16 элементов) переходить к сортировке вставками;
- гибридную стратегию: при малом размере подмассива (обычно 8–16 элементов) переходить к сортировки вставками;
- introsort — алгоритм, начинающийся как быстрая сортировка, но переключающийся на heapsort, если глубина рекурсии превышает пороговое значение (2·log n). Именно introsort (с дополнительным переключением на insertion sort для малых подмассивов) реализован в стандартных библиотеках C++ (
std::sort).
¶Свойства
| Свойство | Значение |
|---|---|
| Средняя сложность | O(n log n) |
| Худшая сложность | O(n²) (у классической версии) |
| Лучшая сложность | O(n log n) |
| Дополнительная память | O(log n) стек вызовов (в худшем случае O(n)) |
| Устойчивость | Нет |
| На месте | Да (с дополнительной памятью под стек) |
Быстрая сортировка неустойчива: равные элементы могут меняться относительным порядком. Устойчивые варианты существуют, но требуют дополнительных затрат.
¶Сравнение с другими алгоритмами
По средней скорости быстрая сортировка обычно превосходит сортировку слиянием и сортировку кучей за счёт лучшей локальности доступа к памяти и меньшего числа сравнений. Сортировка слиянием, в свою очередь, гарантирует O(n log n) в худшем случае, устойчива и удобна для сортировки связных списков. Сортировка кучей также гарантирует O(n log n), но в среднем медленнее быстрой сортировки.
¶Применение
Быстрая сортировка и её вариации (в первую очередь introsort) используются в стандартных библиотеках многих языков программирования. В стандартной библиотеке C++ std::sort реализован на основе introsort. В библиотеке Python list.sort() и sorted() используют тимсорт — гибридную сортировку, основанную на сортировке слиянием и сортировке вставками, однако быстрая сортировка остаётся алгоритмом выбора во многих системных и встраиваемых приложениях, где важна скорость и допустима неустойчивость.
¶История
Алгоритм быстрой сортировки был разработан Чарльзом Хоаром в 1959—1960 годах во время работы над языком программирования ALGOL 60. Схема разделения, предложенная Хоаром, получила название «схема Хоара». В 1962 году Дональд Кнут в своём труде «The Art of Computer Programming» подробно проанализировал алгоритм и его вариации. В 1975 году Джон Ломуто предложил более простую схему разделения, ставшую популярной в учебных материалах.
¶Источники
- Кнут Д. Искусство программирования. Том 3: Сортировка и поиск.
- Хоар Ч. А. Р. «Algorithm 64: Quicksort», Communications of the ACM, 1961.
- Sedgewick Р. Algorithms. — Addison-Wesley.
- Марков М. С., Шишков Ю. Л. Методы сортировки и обработки данных.