Модуль 20 ⏱ ~20 мин чтения 📐 1 Mermaid диаграмм

4. Quick sort

Введение: В погоне за скоростью на месте

В предыдущей главе 3. Merge sort мы познакомились с мощной парадигмой «Разделяй и властвуй». Сортировка слиянием математически безупречна и гарантирует непоколебимые $O(N \log N)$ в любых условиях. Однако для вычислений в оперативной памяти (in-memory) у нее есть существенный архитектурный изъян: требование выделения дополнительного буфера памяти размером $O(N)$. Если сервис сортирует срез на 10 ГБ данных, ему потребуется выделить еще 10 ГБ оперативной памяти просто для того, чтобы перекладывать байты из одного буфера в другой.

Индустрии требовался алгоритм, работающий столь же быстро, но производящий все манипуляции строго на месте (in-place), без обращения к аллокатору кучи. В 1959 году выдающийся британский ученый Тони Хоар изобрел Быструю сортировку (Quick Sort). Сегодня ее модификации служат надежным мотором стандартных библиотек практически всех промышленных языков программирования, включая Go.

Концепция: Разделение вокруг опоры

В то время как Merge Sort сначала механически делит срез пополам, а всю интеллектуальную работу откладывает на фазу слияния, Quick Sort действует с точностью до наоборот. Вся содержательная работа выполняется на этапе разбиения (Partition), после чего фаза «слияния» вообще не требуется.

Алгоритм строится на трех шагах:

  1. Выбор опорного элемента (Pivot): Из подмассива выбирается один элемент, относительно которого будет оцениваться весь набор.
  2. Разделение (Partition): Элементы среза переставляются на месте таким образом, чтобы все значения, меньшие pivot, оказались слева от него, а все значения, большие или равные — справа. В результате этой процедуры сам pivot оказывается на своей окончательной, идеально отсортированной позиции.
  3. Рекурсия: Алгоритм рекурсивно вызывается для независимой обработки левого и правого сегментов.
flowchart TD
    A["Исходный срез:<br/>[8, 3, 1, 7, 0, 10, 2]"] -->|"Шаг 1: Выбор Pivot"| B["Pivot = 7<br/>(Опорный элемент)"]
    B -->|"Шаг 2: Partition"| C["Перестановки на месте (in-place)"]
    C --> D["Меньше Pivot:<br/>[3, 1, 0, 2]"]
    C --> E["Pivot на своем месте:<br/>[7]"]
    C --> F["Больше Pivot:<br/>[8, 10]"]

    D -->|"Шаг 3: Рекурсия"| G["QuickSort(левая часть)"]
    F -->|"Шаг 3: Рекурсия"| H["QuickSort(правая часть)"]

    classDef default fill:#0f172a,stroke:#334155,color:#f8fafc
    classDef step fill:#1e293b,stroke:#38bdf8,color:#38bdf8
    classDef pivot fill:#1e293b,stroke:#10b981,color:#10b981
    classDef branch fill:#1e293b,stroke:#818cf8,color:#f8fafc

    class A default
    class B,C,D,F step
    class E pivot
    class G,H branch

Mechanical Sympathy: Почему Quick Sort действительно "Quick"?

Теоретическая сложность Quick Sort в среднем составляет $O(N \log N)$ — ровно столько же, сколько у Merge Sort. Однако на реальном кремниевом процессоре Quick Sort обгоняет соперника в 2–3 раза. В чем секрет этого феномена?

  1. Идеальная пространственная локальность (Cache Locality): Алгоритм выполняется strictly in-place. Встречные указатели движутся навстречу друг другу, последовательно считывая смежные элементы. Аппаратный предсказатель адресов (Hardware Prefetcher) заполняет кэш-линии (Cache Lines) первого уровня L1-кэша с предельной эффективностью. Никаких блужданий по памяти.
  2. Нулевые аллокации в куче: Алгоритм обходится без вызовов make(). Нет нагрузки на Garbage Collector, нет задержек на выделение страниц памяти.
  3. Минимальный объем перемещения данных: В Merge Sort каждый байт неизбежно копируется из исходного среза во временный буфер и обратно. Quick Sort выполняет лишь точечные парные перестановки (swaps), не покидая границ одного непрерывного блока памяти.

Трагедия худшего случая: $O(N^2)$

Однако у чистой схемы Quick Sort есть драматическая уязвимость. Ее производительность критически зависит от качества выбора опорного элемента (Pivot).

Как индустрия решает проблему Pivot?

В промышленном коде никто не выбирает тривиальный крайний элемент. На практике применяются надежные эвристики:

  1. Случайный Pivot (Randomized Pivot): Выбор псевдослучайного индекса математически гарантирует среднее $O(N \log N)$, однако обращение к генератору случайных чисел в узком цикле создает избыточный оверхед.
  2. Медиана трех (Median of Three): Алгоритм исследует первый, центральный и последний элементы подмассива и выбирает в качестве опоры средний по величине. Эта операция занимает буквально пару инструкций CPU и идеально защищает от деградации на частично упорядоченных массивах.

Идиоматичная реализация на Go

Существует две классические схемы разделения: схема Ломуто (наиболее проста и наглядна) и схема Хоара (выполняет в среднем втрое меньше перестановок). Ниже представлена надежная реализация со схемой Ломуто и оптимизацией «Медиана трех», написанная на современном обобщенном Go (1.21+):

Go 
package sort

import "cmp"

// QuickSort сортирует срез in-place без выделения дополнительной динамической памяти.
func QuickSort[T cmp.Ordered](arr []T) {
    if len(arr) < 2 {
        return
    }
    quickSortRec(arr, 0, len(arr)-1)
}

func quickSortRec[T cmp.Ordered](arr []T, low, high int) {
    if low < high {
        // Оптимизация: Выбор Pivot с помощью "Медианы трех" 
        // надежно защищает от деградации в O-N^2- на упорядоченных срезах.
        pivotIdx := medianOfThree(arr, low, high)

        // Прячем pivot в конец, чтобы алгоритм Ломуто сработал стандартно
        arr[pivotIdx], arr[high] = arr[high], arr[pivotIdx]

        // Выполняем разделение
        p := partition(arr, low, high)

        // Рекурсивно сортируем левую и правую части.
        // Элемент под индексом 'p' уже находится на своем финальном месте!
        quickSortRec(arr, low, p-1)
        quickSortRec(arr, p+1, high)
    }
}

// partition переставляет элементы и возвращает финальный индекс pivot
func partition[T cmp.Ordered](arr []T, low, high int) int {
    pivot := arr[high]
    i := low // i указывает на границу элементов, которые строго меньше pivot

    for j := low; j < high; j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    // Ставим pivot на его законное место
    arr[i], arr[high] = arr[high], arr[i]
    return i
}

// medianOfThree находит индекс среднего по значению элемента
// среди первого, центрального и замыкающего.
func medianOfThree[T cmp.Ordered](arr []T, low, high int) int {
    mid := low + (high-low)/2

    // Сортируем три элемента между собой прямо в массиве
    if arr[low] > arr[mid] {
        arr[low], arr[mid] = arr[mid], arr[low]
    }
    if arr[low] > arr[high] {
        arr[low], arr[high] = arr[high], arr[low]
    }
    if arr[mid] > arr[high] {
        arr[mid], arr[high] = arr[high], arr[mid]
    }

    // Теперь arr-mid- содержит медиану
    return mid
}

Собеседование: Главные вопросы

Итог

  • Quick Sort — общепризнанный лидер среди алгоритмов сортировки в оперативной памяти благодаря исключительной кэш-локальности и отсутствию аллокаций.
  • Слабость: Теоретический риск деградации в $O(N^2)$ при неудачном выборе опорного элемента. В продакшене проблема нивелируется эвристиками вроде «Медианы трех» и гибридизацией в pdqsort.
  • Память: Работает in-place, но расходует $O(\log N)$ памяти стека вызовов (Call Stack).
  • Стабильность: Нестабилен (Unstable).

Если вашей системе требуется абсолютная, математически нерушимая гарантия $O(N \log N)$ без малейшего риска деградации и с нулевыми требованиями к дополнительной динамической памяти, на помощь приходит алгоритм, основанный на двоичной куче.

В следующей статье мы разберем пирамидальную сортировку: 5. Heap sort.