Содержание
Как работает быстрая сортировка
Черновик готовит редакция с помощью ИИ. За стандарт издания отвечает главный редактор — Валерий Курземнек.
Быстрая сортировка (quicksort) — алгоритм класса «разделяй и властвуй»: выбирается опорный элемент, массив делится на части «меньше опорного» и «больше опорного», после чего те же шаги рекурсивно применяются к каждой части. Средняя сложность — O(n log n). Алгоритм придумал британский учёный Тони Хоар в 1960 году. Ниже разберём принцип, разбиение по шагам, реализацию на Python и сравнение с другими сортировками.
Принцип работы
Быстрая сортировка использует стратегию «разделяй и властвуй». Алгоритм состоит из трёх основных шагов:
- Выбор опорного элемента. Из массива выбирается один элемент, который будет служить опорным (pivot). Критерии выбора могут различаться: первый элемент, последний, средний или выбранный случайным образом.
- Разбиение (partition). Массив перестраивается так, что элементы меньше опорного помещаются перед ним, а большие или равные — после. После этого опорный элемент стоит на своей конечной позиции в готовом массиве.
- Рекурсия. Те же два шага применяются к двум подмассивам, образованным слева и справа от опорного. Рекурсию не применяют к массиву из одного элемента — он уже отсортирован.
Алгоритм разработал Тони Хоар в 1960 году во время работы в МГУ — изначально для задачи машинного перевода. С тех пор quicksort остаётся одним из самых используемых методов сортировки в стандартных библиотеках языков программирования.
Разбиение по шагам на примере
![Разбиение массива [3, 6, 8, 10, 1, 2, 1], опорный — последний элемент](https://ya.zerocoder.ru/wp-content/uploads/2026/06/scheme-17200-1-hd.png)
Разберём один проход на массиве [3, 6, 8, 10, 1, 2, 1]. В качестве опорного возьмём последний элемент. Сначала массив делится относительно опорного, затем те же шаги повторяются для левой и правой частей, пока в подмассиве не останется один элемент.
- Опорный элемент — 1 (последний). Все остальные элементы сравниваются с ним.
- Элементы меньше или равные опорному уходят влево: [1]. Большие — вправо: [3, 6, 8, 10, 2].
- Левая часть [1] состоит из одного элемента — она уже отсортирована.
- Правая часть [3, 6, 8, 10, 2] обрабатывается рекурсивно: выбирается новый опорный и снова идёт разбиение.
- Результаты собираются в порядке «левое + опорный + правое» — получается отсортированный массив [1, 1, 2, 3, 6, 8, 10].
Особенности и преимущества
- Эффективность на больших данных. Средняя временная сложность — O(n log n), что делает quicksort одной из самых быстрых сортировок для больших объёмов данных.
- Сортировка на месте. Оптимизированная реализация требует лишь O(log n) дополнительной памяти под стек рекурсии, не выделяя новые массивы.
- Адаптивность. Производительность сильно зависит от выбора опорного элемента — при удачном выборе алгоритм работает близко к лучшему случаю.
- Нестабильность. Quicksort не сохраняет относительный порядок равных элементов — это плата за скорость.
Схемы разбиения: Ломуто и Хоара
Разбиение можно реализовать по-разному. Две классические схемы:
- Схема Ломуто. Использует один указатель i. Опорным обычно берётся последний элемент. Алгоритм проходит массив и каждый элемент, не больший опорного, переносит в левую часть. Проще для понимания, но делает больше обменов.
- Схема Хоара. Использует два указателя — с начала и с конца массива, которые движутся навстречу друг другу и меняют местами пары элементов, стоящих «не на своей стороне». Эффективнее по числу обменов, но сложнее в реализации.
Реализация на Python
Начнём с самой наглядной версии. Этот пример использует рекурсию и list comprehension: опорным берётся последний элемент, а вспомогательные списки собирают элементы меньше и больше опорного.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr.pop() # последний элемент как опорный
lesser_than_pivot = [] # элементы меньше или равные опорному
greater_than_pivot = [] # элементы больше опорного
for element in arr:
if element > pivot:
greater_than_pivot.append(element)
else:
lesser_than_pivot.append(element)
# рекурсивно сортируем подмассивы и склеиваем результат
return quick_sort(lesser_than_pivot) + [pivot] + quick_sort(greater_than_pivot)
# Пример использования
arr = [3, 6, 8, 10, 1, 2, 1]
print("Готовый массив:", quick_sort(arr))
Этот код прост для чтения, но создаёт дополнительные списки на каждом уровне рекурсии. Для экономии памяти применяют разбиение «на месте» по схеме Ломуто — массив сортируется внутри себя, без вспомогательных списков:
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
p = partition(arr, low, high) # опорный встаёт на своё место
quick_sort(arr, low, p - 1) # сортируем левую часть
quick_sort(arr, p + 1, high) # сортируем правую часть
return arr
def partition(arr, low, high):
pivot = arr[high] # опорный — последний элемент
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
Обе функции дают один результат — отсортированный массив [1, 1, 2, 3, 6, 8, 10]. Первая удобнее для обучения, вторая ближе к тому, как quicksort реализуют на практике.
Как узнать быструю сортировку в чужом коде
Если перед вами какая-то реализация алгоритма быстрой сортировки, её выдают характерные признаки:
- есть выбор опорного элемента (pivot) — первого, последнего, среднего или случайного;
- массив делится на части относительно опорного (функция partition или сборка списков «меньше/больше»);
- функция вызывает сама себя для левой и правой части — это рекурсия;
- результат получается склейкой подмассивов или сортировкой на месте через обмены элементов.
Худший случай и как его избежать
В среднем quicksort работает за O(n log n), но в худшем случае деградирует до O(n²). Это происходит, когда опорный элемент стабильно оказывается самым маленьким или самым большим — например, при сортировке уже упорядоченного массива с выбором крайнего элемента в качестве опорного. Тогда массив делится крайне неравномерно. Снизить риск помогают:
- Случайный опорный элемент — рандомизация ломает «плохие» входные данные.
- Медиана трёх — опорным берётся медиана из первого, среднего и последнего элементов.
- Introsort — гибрид, который при слишком глубокой рекурсии переключается на пирамидальную сортировку (heap sort) и гарантирует O(n log n).
Сравнение с другими методами
По сравнению с сортировкой слиянием quicksort на практике часто быстрее, хотя у обоих средняя сложность O(n log n). В отличие от слияния, быстрая сортировка не требует значительной дополнительной памяти, что делает её предпочтительной в системах с ограниченным объёмом памяти. Сравним основные алгоритмы по сложности, памяти и стабильности.
| Алгоритм сортировки | Лучший случай | Средний случай | Худший случай | Дополнительная память | Стабильность |
| Быстрая сортировка | O(n log n) | O(n log n) | O(n²) | O(log n) | Нестабильная |
| Сортировка слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | Стабильная |
| Пузырьковая сортировка | O(n) | O(n²) | O(n²) | O(1) | Стабильная |
| Сортировка вставками | O(n) | O(n²) | O(n²) | O(1) | Стабильная |
| Сортировка выбором | O(n²) | O(n²) | O(n²) | O(1) | Нестабильная |
Объяснение терминов
- Временная сложность — мера количества операций для сортировки массива. Показывает, как растёт время выполнения с увеличением размера входных данных.
- Дополнительная память — объём памяти, который требуется алгоритму помимо исходного массива.
- Стабильность — алгоритм стабилен, если сохраняет относительный порядок одинаковых элементов.
Выводы
- Быстрая сортировка и сортировка слиянием дают хорошую производительность на больших данных, но слияние требует значительно больше дополнительной памяти.
- Пузырьковая и вставками подходят для небольших или почти отсортированных массивов, но неэффективны на больших данных.
- Сортировка выбором имеет квадратичную сложность независимо от входных данных и в целом медленнее остальных рассмотренных методов.
Частые вопросы
Кто придумал быструю сортировку?
Алгоритм разработал британский учёный Тони Хоар в 1960 году во время работы в МГУ. Поэтому быструю сортировку также называют сортировкой Хоара.
Какая сложность у быстрой сортировки?
В среднем и лучшем случае — O(n log n), в худшем — O(n²). Дополнительной памяти в оптимизированной версии требуется O(log n) под стек рекурсии.
Почему быстрая сортировка может работать за O(n²)?
Когда опорный элемент стабильно оказывается минимальным или максимальным (например, на уже отсортированном массиве), разбиение получается неравномерным. Помогают случайный выбор опорного, метод «медианы трёх» или introsort.
Стабильна ли быстрая сортировка?
Нет. В классических реализациях относительный порядок равных элементов не сохраняется.
Чем схема Ломуто отличается от схемы Хоара?
Схема Ломуто использует один указатель и проще в реализации, но делает больше обменов. Схема Хоара использует два встречных указателя и эффективнее по числу обменов.
Заключение
Быстрая сортировка — мощный и универсальный алгоритм, который применяется во множестве задач обработки данных благодаря эффективности и простоте реализации. Способность работать с большими объёмами данных и минимальные требования к дополнительной памяти делают quicksort одним из лучших инструментов в арсенале программиста. Главное — следить за выбором опорного элемента, чтобы не попасть в худший случай. Подробнее об истории и схемах разбиения можно прочитать в Википедии.