Быстрая сортировка представляет собой эффективный алгоритм, основанный на стратегии «разделяй и властвуй». Представьте себе задачу упорядочить книги на полке по высоте. Вместо того чтобы последовательно сравнивать каждую книгу с каждой, что потребовало бы значительного времени, можно выбрать одну книгу среднего размера в качестве условного эталона. Все книги меньше этого эталона помещаются слева, а все больше — справа. Затем эта же процедура рекурсивно применяется к каждой из образовавшихся групп. Именно эта идея лежит в основе быстрой сортировки.
Алгоритм работает, разделяя исходный массив данных на части относительно специально выбранного элемента, который называется опорным или пивотом. Стратегия «разделяй и властвуй» подразумевает три этапа: сначала большую задачу разбивают на меньшие независимые подзадачи, затем каждую из них решают, и наконец, полученные решения объединяют в окончательный результат. Этот процесс можно представить как преобразование большого беспорядка в несколько маленьких, которые затем приводятся в порядок.
Рассмотрим работу алгоритма пошагово на примере массива
[64, 34, 25, 12, 22, 11, 90]. Первым шагом является выбор опорного элемента. Это может быть первый, последний, средний или случайный элемент массива. В нашем примере выберем средний элемент по индексу: arr[3] = 12.Второй шаг — разделение массива. Все элементы, меньшие опорного, помещаются в одну группу, равные ему — в другую, а большие — в третью.
Меньше 12: [11]
Равно 12: [12]
Больше 12: [64, 34, 25, 22, 90]
Наглядно это можно изобразить так:
[64, 34, 25, 12, 22, 11, 90]
↓
выбираем pivot = 12
↓
┌─────────────────┼─────────────────┐
↓ ↓ ↓
[11] [12] [64, 34, 25, 22, 90]
(меньше) (равно) (больше)
Третий шаг — рекурсивное применение того же алгоритма к левой и правой частям, так как группа равных опорному элементу уже считается отсортированной. Для левой части
[11], состоящей из одного элемента, рекурсия завершается. Для правой части [64, 34, 25, 22, 90] снова выбирается опорный элемент, например, средний — 25, и процесс разделения повторяется.Четвертый шаг — объединение результатов. После того как все рекурсивные вызовы завершены, отсортированные части собираются вместе. Сборка происходит снизу вверх: отсортированные подмассивы меньших размеров объединяются с опорными элементами.
Уровень 4: [] + [64] + [90] = [64, 90]
Уровень 3: [] + [34] + [64, 90] = [34, 64, 90]
Уровень 2: [22] + [25] + [34, 64, 90] = [22, 25, 34, 64, 90]
Уровень 1: [11] + [12] + [22, 25, 34, 64, 90] = [11, 12, 22, 25, 34, 64, 90]
Полное дерево рекурсии для данного примера выглядит следующим образом:
[64, 34, 25, 12, 22, 11, 90]
pivot=12
/ | \
[11] [12] [64, 34, 25, 22, 90]
↓ pivot=25
[11] / | \
[22] [25] [64, 34, 90]
↓ pivot=34
[22] / | \
[] [34] [64, 90]
pivot=64
/ | \
[] [64] [90]
↓
[90]
Сборка снизу вверх:
[11] + [12] + ([22] + [25] + ([] + [34] + ([] + [64] + [90])))
= [11, 12, 22, 25, 34, 64, 90]
Реализация этого алгоритма на Python демонстрирует его лаконичность. Ключевая часть — рекурсивное разделение и объединение массивов.