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

Быстрая сортировка (Quick Sort): выбор опорного элемента, разбиение Lomuto, рекурсия, код на Python, O(n log n) в среднем и O(n²) в худшем случае.

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

Сложность: O(n log n) в среднем; O(n²) в худшем случае; O(1) дополнительной памяти (in-place).

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

Выбираем один элемент — pivot. Переставляем массив так, чтобы слева стояли элементы меньше pivot, а справа — больше (сам pivot попадает на своё финальное место). Затем рекурсивно применяем тот же приём к обеим частям. Когда каждая часть содержит ≤1 элемента, всё отсортировано.

Пошаговый разбор (разбиение Lomuto)

Массив [10, 80, 30, 90, 40, 50, 70], pivot = последний элемент (70):

Начало: [10, 80, 30, 90, 40, 50, 70]  pivot=70
i = -1 (граница «меньше»)

j=0: arr[0]=10 < 70 → i=0, обмен[0,0] → [10, 80, 30, 90, 40, 50, 70]
j=1: arr[1]=80 > 70 → пропуск
j=2: arr[2]=30 < 70 → i=1, обмен[1,2] → [10, 30, 80, 90, 40, 50, 70]
j=3: arr[3]=90 > 70 → пропуск
j=4: arr[4]=40 < 70 → i=2, обмен[2,4] → [10, 30, 40, 90, 80, 50, 70]
j=5: arr[5]=50 < 70 → i=3, обмен[3,5] → [10, 30, 40, 50, 80, 90, 70]

Ставим pivot: обмен[4, 6] → [10, 30, 40, 50, 70, 90, 80]
pivot (70) на месте! Сортируем [10,30,40,50] и [90,80] отдельно.

Код

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
    return arr


def partition(arr, low, high):
    pivot = arr[high]   # опорный — последний элемент (схема Lomuto)
    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


data = [10, 80, 30, 90, 40, 50, 70]
print(quick_sort(data))

Вывод:

[10, 30, 40, 50, 70, 80, 90]

Сложность и свойства

Случай	Время	Память (стек)
Лучший (pivot делит пополам)	O(n log n)	O(log n)
Средний	O(n log n)	O(log n)
Худший (pivot всегда крайний)	O(n²)	O(n)

In-place (O(1) дополнительного массива), но рекурсивный стек занимает O(log n). Алгоритм неустойчивый.

Худший случай возникает, когда pivot всегда оказывается минимальным или максимальным (например, уже отсортированный массив с pivot = последний элемент). Решение — случайный выбор pivot или метод «медиана трёх».

Когда применять

На практике быстрая сортировка быстрее merge sort за счёт низких констант и хорошей работы с кешем.
Стандартная библиотека C++ (std::sort) и Python (Timsort включает идеи quick sort) используют её варианты.
Не подходит, когда нужна устойчивость или гарантированное O(n log n) — там merge sort.

Коротко

Quick sort выбирает опорный элемент, делит массив на «меньше» и «больше», рекурсивно сортирует обе части.
O(n log n) в среднем, O(n²) в худшем — избегают случайным выбором pivot.
In-place, неустойчивый, на практике самый быстрый из классических.