Быстрая сортировка – Учебник

10.4

О чём этот урок

Представьте стопку из тысячи карточек, которую надо разложить по алфавиту. Работа кажется неподъёмной, пока не сделать одно грубое движение: раскидать стопку на две – «до буквы М» и «от М». Точность не нужна: теперь это две независимые задачи по пятьсот карточек, и ни одна карточка не переедет из стопки в стопку. Каждую половину можно разобрать так же.

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

После разбиения опорный элемент стоит на своём окончательном месте: слева от него только те элементы, которым положено быть слева, справа – те, которым положено быть справа.

Дальше остаётся разобрать две части по отдельности, и каждая короче исходного отрезка. Деление заканчивается само, когда в части остаётся один элемент.

Приём придумал Тони Хоар в 1960 году.

В этом уроке: разбиение на месте, программа со списком неразобранных отрезков, цена $N \log N$ в среднем и $O(N^2)$ в худшем случае; почему быстрая сортировка не устойчива.

Разбиение на месте

Опорным берём последний элемент отрезка. Идём по отрезку слева направо и держим одну границу i – позицию, по которую уже собраны все маленькие элементы.

Встретили элемент меньше опорного – граница сдвигается вправо, и найденный элемент меняется местами с тем, кто стоял на этой позиции.
Встретили элемент больше опорного – ничего не делаем, он и так остаётся в правой части.

В конце опорный меняют с первым элементом справа от границы – и он оказывается между группами. На списке [5, 1, 4, 2, 8, 3] с опорным 3 это выглядит так.

Смотрим	Сравнение	Что делаем	Список
5	5 > 3	ничего	`5 1 4 2 8 3`
1	1 < 3	граница на позицию 0, меняем 5 и 1	`1 5 4 2 8 3`
4	4 > 3	ничего	`1 5 4 2 8 3`
2	2 < 3	граница на позицию 1, меняем 5 и 2	`1 2 4 5 8 3`
8	8 > 3	ничего	`1 2 4 5 8 3`
–	–	меняем 4 и 3	`1 2 3 5 8 4`

Тройка на окончательном месте, слева от неё 1 2, справа 5 8 4.

Разбиение отрезка длины m стоит m − 1 сравнений: один проход, каждый элемент сравнивается с опорным один раз.

Программа целиком

Разбиение обрабатывает один отрезок. Дальше то же надо сделать с обеими половинами. Программа хранит список ещё не разобранных отрезков tasks: берёт очередной, разбивает и добавляет два новых. Обычно этот алгоритм пишут рекурсией, её разберём в блоке 11 (урок 11.3).

a = [5, 1, 4, 2, 8, 3]
tasks = [[0, len(a) - 1]]

while len(tasks) > 0:
    task = tasks.pop()
    lo = task[0]
    hi = task[1]
    if lo >= hi:
        continue

    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    p = i + 1

    tasks.append([lo, p - 1])
    tasks.append([p + 1, hi])

print(a)
# [1, 2, 3, 4, 5, 8]

Разбор строк:

tasks.pop() снимает последний отрезок; порядок разбора на результат не влияет.
if lo >= hi: continue – отрезок из одного элемента уже упорядочен, без этой проверки программа зациклилась бы.
a[j] < pivot – строгое сравнение: равные опорному остаются справа.
a[i + 1], a[hi] = a[hi], a[i + 1] ставит опорный между группами и фиксирует его место в p.
Новые отрезки не включают p, поэтому каждый строго короче исходного.

Сколько это стоит

Считать отдельные разбиения бесполезно, считать надо уровни деления. На каждом уровне отрезки вместе содержат почти те же N элементов, поэтому один уровень стоит примерно N сравнений. Если опорный каждый раз делит отрезок пополам, уровней около $\log_2 N$.

В среднем быстрая сортировка делает порядка $N \log N$ сравнений.

Для 1000 случайных чисел $N \cdot \log_2 N = 9\,966$, а программа делает 11 460 сравнений: тот же порядок, разница только в постоянном множителе.

N	Время	Во сколько раз больше
10 000	0,011 с	–
20 000	0,023 с	2,2
40 000	0,050 с	2,1
80 000	0,105 с	2,1
160 000	0,240 с	2,3

Данных вдвое больше – времени чуть больше чем вдвое. Миллион случайных чисел этот код сортирует примерно за 3 с на чистом Python.

Худший случай

Экономия держалась на том, что опорный делит отрезок пополам. Никто этого не обещал. Если опорный – максимум отрезка, левая часть забирает весь отрезок, а правая остаётся пустой: отрезок укорачивается на один элемент.

С нашим выбором «опорный – последний» это случается на уже упорядоченном списке: последний элемент упорядоченного отрезка и есть максимум. Сравнений тогда $N \cdot (N-1)/2$, то есть $O(N^2)$.

N (список уже упорядочен)	Время	Во сколько раз больше
1 000	0,033 с	–
2 000	0,136 с	4,1
4 000	0,555 с	4,1
8 000	2,23 с	4,0

Те же 8 000 элементов в разном порядке: случайный – 0,008 с, уже упорядоченный – 2,23 с, обратный – 1,60 с.

Лекарство – выбирать опорным средний или случайный элемент отрезка. В коде это одна дописанная строка перед разбиением:

mid = (lo + hi) // 2
a[mid], a[hi] = a[hi], a[mid]

Дальше всё работает как было: опорный по-прежнему лежит в a[hi], но выбран он уже не по краю.

Свойства

На месте. Копий данных нет: программа держит только список ожидающих отрезков, а элементы переставляются внутри исходного списка.
Неустойчива. Элементы прыгают через полсписка и могут перескочить через равного себе; сортировать в два захода, как в уроке 10.6, с ней нельзя.
На практике она одна из самых быстрых: разбиение идёт подряд по соседним ячейкам памяти, а такой доступ процессор обслуживает быстрее произвольных прыжков.
Быстрее чем за порядок $N \log N$ сравнений отсортировать нельзя никаким алгоритмом, который только сравнивает элементы.

Коротко