5.10 — Быстрая сортировка (QuickSort)

Сегодня мы познакомимся с одним из самых красивых и быстрых алгоритмов сортировки — быстрой сортировкой.

Она была придумана в 1960 году в МГУ британским учёным Энтони Хоаром. С тех пор этот алгоритм стал одним из самых популярных в мире и используется даже в стандартных библиотеках многих языков программирования.

Идея алгоритма

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

слева оказались все числа меньше или равные pivot;
справа — все числа больше pivot.

Рекурсивно повторяем сортировку для левой и правой части.

Таким образом, мы шаг за шагом делим задачу на всё меньшие и меньшие кусочки, пока массив полностью не отсортируется.

Важные детали

Опорный элемент можно выбирать разными способами (например, последний элемент, центральный или случайный). От этого зависит скорость работы.
Когда мы переносим элементы относительно опорного, то сам pivot тоже может двигаться: например, если он оказался самым большим, то он уходит вправо.
Алгоритм нестабилен, то есть одинаковые элементы могут поменяться местами.

Вариант 1. Реализация с буфером

Простейшая версия быстрой сортировки: мы выбираем pivot, создаём новый массив (буфер) и складываем туда элементы в правильном порядке — сначала меньшие pivot, потом сам pivot, затем остальные. После этого копируем результат обратно.

Этот способ легко понять, но он требует дополнительной памяти.

Вариант 2. Разбиение Ломуто (in-place)

Более интересный и практичный вариант называется разбиение Ломуто. В нём мы не используем буфер, а просто переставляем элементы прямо внутри массива.

Как это работает:

Берём pivot = последний элемент.
Создаём специальный маркер p_index, который сначала указывает на начало массива.
Перебираем все элементы:
если текущий элемент меньше или равен pivot, меняем его местами с элементом на позиции p_index, и двигаем маркер вправо;
если больше pivot, ничего не делаем.

В конце p_index указывает на то место, куда встанет pivot. Таким образом, массив делится на две части: слева всё меньше pivot, справа — всё больше.

Пример работы разбиения

Допустим, у нас есть массив:

[1, 10, 2, 5, 3, 6, 4, 9, 8, 7]

Опорный элемент — последний, то есть 7.

Сначала p_index = 0, i = 0.
1 меньше 7, значит, делаем обмен (ничего не изменилось, потому что 1 и так на месте) и сдвигаем p_index.
Теперь p_index = 1, i = 1.
10 больше 7 → i просто двигается дальше.
На шаге i = 2 число 2 меньше 7, значит, обмениваем его с элементом на позиции p_index (1), и двигаем p_index.

И так продолжаем до конца массива. В итоге pivot оказывается на своём месте, а массив делится на две части:

[1, 2, 5, 3, 6, 4, 7, 9, 8, 10]

Сложность алгоритма

В среднем случае (если pivot делит массив примерно пополам):
мы делим массив на два и повторяем сортировку для половинок. Получаем:
O(n · log₂ n)
В худшем случае (если pivot всегда оказывается самым большим или самым маленьким):
массив не делится, и приходится сортировать всё снова и снова. Тогда сложность:
O(n²)
На практике быстрая сортировка работает очень быстро, поэтому её часто используют.

Итоги

Быстрая сортировка — рекурсивный алгоритм.
Работает в среднем за O(n log n), что делает её одной из самых быстрых.
Может работать прямо в массиве, не занимая лишнюю память.
Но алгоритм нестабилен и в худшем случае может работать за O(n²).

Пример 1. Быстрая сортировка для обычного списка Python

# Быстрая сортировка для списка Python
def quick_sort(arr):
    # Базовый случай: если список пустой или из одного элемента
    if len(arr) <= 1:
        return arr
    
    pivot = arr[-1]  # выбираем последний элемент как опорный
    left = [x for x in arr[:-1] if x <= pivot]   # элементы меньше или равны pivot
    right = [x for x in arr[:-1] if x > pivot]   # элементы больше pivot
    
    # Рекурсивно сортируем левую и правую части и объединяем
    return quick_sort(left) + [pivot] + quick_sort(right)

# Пример использования
data = [1, 10, 2, 5, 3, 6, 4, 9, 8, 7]
print("Оригинальный список:", data)
sorted_data = quick_sort(data)
print("Отсортированный список:", sorted_data)

Пример 2. Быстрая сортировка с NumPy

import numpy as np

def quick_sort_numpy(arr):
    # Если массив пустой или из одного элемента
    if arr.size <= 1:
        return arr
    
    pivot = arr[-1]  # опорный элемент (последний)
    
    # Разделяем массив на элементы меньше/больше pivot
    left = arr[arr[:-1] <= pivot]
    right = arr[arr[:-1] > pivot]
    
    # Рекурсивно сортируем левую и правую части
    return np.concatenate((quick_sort_numpy(left), [pivot], quick_sort_numpy(right)))

# Пример использования
data_np = np.array([1, 10, 2, 5, 3, 6, 4, 9, 8, 7])
print("Оригинальный массив:", data_np)
sorted_np = quick_sort_numpy(data_np)
print("Отсортированный массив:", sorted_np)

В чём разница:

В версии с Python-списком мы используем генераторы списков ([x for x in arr ...]).
В NumPy-версии мы используем булевы маски (arr[arr <= pivot]), которые делают выборку элементов.
Обе версии работают одинаково по смыслу, но NumPy-версия удобна для работы с числовыми массивами.

Быстрая сортировка (QuickSort)

Материал урока