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

Идея: разделяй и властвуй

Представьте, что вам нужно рассадить по местам большую группу людей на трибуне — от самого младшего к самому старшему, а людей несколько сотен. Перебирать их по одному и сравнивать каждого с каждым долго. Умнее поступить иначе: выбрать одного человека как ориентир, попросить всех, кто младше него, встать слева, а кто старше — справа. Внутри каждой группы повторить тот же приём. Через несколько таких делений вся трибуна окажется отсортирована, а сравнений понадобится гораздо меньше, чем при переборе всех пар.

Именно так работает быстрая сортировка (по-английски quick sort). Официально такой подход называется «разделяй и властвуй» (divide and conquer): большая задача разбивается на несколько похожих задач меньшего размера, каждая решается сама по себе, а затем результаты собираются вместе. Раньше, когда вы разбирали пузырьковую сортировку, каждый элемент сравнивался почти с каждым — поэтому она такая медленная. Быстрая сортировка вместо этого делит массив на части и решает задачу для каждой части отдельно, а собирает результат так, как вы уже умеете собирать списки через +.

Шаги алгоритма такие:

Опорный элемент (pivot)

Тот самый элемент-ориентир, который вы выбираете на первом шаге, имеет официальное название — опорный элемент, или pivot (от английского «точка опоры»). От него зависит, насколько ровно массив разделится на две части.

Взять можно любой элемент массива — первый, последний, средний или вообще случайный. Разница в том, что если постоянно выбирать неудачный pivot (например, всегда самый маленький элемент), деление получится неровным: одна часть будет почти пустой, а другая — почти всем массивом. Тогда сортировка станет такой же медленной, как пузырьковая. Если же pivot делит массив примерно пополам, сортировка работает быстро. Проще всего для начала брать последний элемент списка — так и поступим в первой реализации, а чуть позже посмотрим на pivot, который выбирается случайно.

Реализация на Python

На Python быстрая сортировка записывается очень коротко, потому что генераторы списков умеют сразу отобрать нужные элементы в новый список.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[-1]
    rest = arr[:-1]

    less = [x for x in rest if x < pivot]
    equal = [x for x in rest if x == pivot]
    greater = [x for x in rest if x > pivot]

    equal.append(pivot)
    return quick_sort(less) + equal + quick_sort(greater)

Разберём построчно:

Проверим на примере:

numbers = [3, 6, 8, 10, 1, 2, 1]
result = quick_sort(numbers)
print(result)

Проследим первый шаг вручную. Массив — [3, 6, 8, 10, 1, 2, 1], pivot — последний элемент, то есть 1. Оставшаяся часть rest — [3, 6, 8, 10, 1, 2]. Меньше 1 среди них нет ни одного, поэтому less пуст. Равен 1 один элемент, equal получается [1], а после equal.append(pivot) — [1, 1]. Всё остальное больше 1, значит greater — это [3, 6, 8, 10, 2]. Дальше функция вызовет сама себя для less (пустой список, вернётся сразу) и для greater, и там повторится та же логика, пока части не станут длиной 0 или 1.

Ещё один способ выбрать pivot — случайный элемент, а не последний. Он полезен, если на вход часто попадают уже отсортированные списки: тогда «всегда последний» регулярно даёт неудачное деление, а случайный выбор эту проблему снимает.

def quick_sort_random(arr):
    import random

    if len(arr) <= 1:
        return arr

    pivot = random.choice(arr)
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]

    return quick_sort_random(less) + equal + quick_sort_random(greater)

Здесь две отличия от первого варианта. Во-первых, pivot = random.choice(arr) — модуль random вы уже использовали раньше, функция choice берёт из списка один случайный элемент. Во-вторых, генераторы less, equal, greater перебирают весь arr, а не срез без последнего элемента: раз pivot выбран случайно и может оказаться где угодно в списке, срез arr[:-1] тут не подходит — проще пройти по всему массиву и позволить pivot самому попасть в equal при сравнении x == pivot. Поэтому строку equal.append(pivot) здесь добавлять не нужно — он и так уже там.

Насколько это быстрее пузырька

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

Но есть и худший случай — O(n²), такой же, как у пузырька. Он возникает, если pivot раз за разом оказывается самым маленьким или самым большим элементом — ровно тот случай с отсортированным массивом и pivot «всегда последний», который разобрали выше. Тогда деление неровное, и выигрыш от «разделяй и властвуй» исчезает.

Есть у быстрой сортировки и своя цена: рекурсия занимает память — каждый вложенный вызов quick_sort добавляет запись в стек вызовов, пока не дойдёт до базового случая. В среднем случае глубина этого стека — около log n, поэтому дополнительная память — порядка O(log n). Это немного, но не ноль — в отличие от пузырьковой сортировки, где ничего, кроме исходного списка, не хранится.

Частые ошибки

def quick_sort(arr):
    pivot = arr[-1]  # если arr пустой, здесь будет ошибка
    ...

pivot = arr[-1]
less = [x for x in arr if x < pivot]  # перебор всего arr
equal = [x for x in arr[:-1] if x == pivot]  # а тут срез

return quick_sort(less) + quick_sort(greater)  # где pivot?