MidТеория10 min

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

Quick Sort: partition, выбор pivot, worst case и оптимизации

AlgoSorting

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

Идея

  1. Выбрать опорный элемент (pivot)
  2. Partition: переставить элементы так, чтобы меньшие были слева, большие справа
  3. Рекурсивно отсортировать левую и правую части
[3, 6, 8, 10, 1, 2, 1]   pivot = 3

Partition:
[1, 2, 1] [3] [6, 8, 10]
  < pivot   =   > pivot

Рекурсия на каждую часть...

Реализация (Lomuto partition)

<?php
declare(strict_types=1);

/** @param list<int> $arr */
function quickSort(array &$arr, int $low = 0, ?int $high = null): void
{
    if ($high === null) {
        $high = count($arr) - 1;
    }

    if ($low < $high) {
        $pivotIdx = partition($arr, $low, $high);
        quickSort($arr, $low, $pivotIdx - 1);
        quickSort($arr, $pivotIdx + 1, $high);
    }
}

function partition(array &$arr, int $low, int $high): int
{
    $pivot = $arr[$high]; // Take last element as pivot
    $i = $low - 1;       // Boundary of "small" elements

    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] <= $pivot) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        }
    }

    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];

    return $i + 1;
}
## Визуализация Partition 
arr = [8, 3, 1, 7, 0, 10, 2], pivot = 2 (последний)

i = -1
j=0: arr[0]=8 > 2, skip
j=1: arr[1]=3 > 2, skip
j=2: arr[2]=1 <= 2, i=0, swap(0,2) -> [1, 3, 8, 7, 0, 10, 2]
j=3: arr[3]=7 > 2, skip
j=4: arr[4]=0 <= 2, i=1, swap(1,4) -> [1, 0, 8, 7, 3, 10, 2]
j=5: arr[5]=10 > 2, skip

swap(i+1, high) = swap(2, 6) -> [1, 0, 2, 7, 3, 10, 8]
                                        ^
                                     pivot на месте!
[1, 0] < 2 < [7, 3, 10, 8]

Hoare Partition (более эффективная)

<?php
declare(strict_types=1);

function hoarePartition(array &$arr, int $low, int $high): int
{
    $pivot = $arr[$low];
    $i = $low - 1;
    $j = $high + 1;

    while (true) {
        do {
            $i++;
        } while ($arr[$i] < $pivot);

        do {
            $j--;
        } while ($arr[$j] > $pivot);

        if ($i >= $j) {
            return $j;
        }

        [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
    }
}
## Выбор Pivot

Плохой выбор pivot приводит к O(n²). Стратегии:

<?php
declare(strict_types=1);

// 1. Last element (Lomuto) — bad for sorted arrays
$pivot = $arr[$high];

// 2. Random — good on average
$randIdx = random_int($low, $high);
[$arr[$randIdx], $arr[$high]] = [$arr[$high], $arr[$randIdx]];
$pivot = $arr[$high];

// 3. Median of three — good compromise
function medianOfThree(array &$arr, int $low, int $high): int
{
    $mid = intdiv($low + $high, 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]];
    }
    // Now $arr[$mid] is the median
    [$arr[$mid], $arr[$high - 1]] = [$arr[$high - 1], $arr[$mid]];

    return $arr[$high - 1];
}
## Worst Case 
Отсортированный массив + pivot = последний:
[1, 2, 3, 4, 5], pivot = 5

Partition: [] [5] [1, 2, 3, 4]
           0 элементов слева, n-1 справа

Дерево рекурсии:        Сбалансированное:
n                          n
  n-1                    n/2  n/2
    n-2                n/4 n/4 n/4 n/4
      n-3              ...
        ...
Глубина n -> O(n²)     Глубина log n -> O(n log n)

Сложность

Случай Время Когда
Лучший O(n log n) Pivot всегда в середине
Средний O(n log n) Случайный pivot
Худший O(n²) Pivot всегда min/max

Память: O(log n) для стека рекурсии (в среднем), O(n) в худшем.

Quick Select: k-й элемент за O(n)

Модификация Quick Sort для поиска k-го наименьшего элемента:

<?php
declare(strict_types=1);

/** Find k-th smallest element (1-indexed) */
function quickSelect(array &$arr, int $k): int
{
    $k--; // 0-indexed

    $select = function (int $low, int $high) use (&$select, &$arr, $k): int {
        if ($low === $high) {
            return $arr[$low];
        }

        $pivotIdx = partition($arr, $low, $high);

        if ($pivotIdx === $k) {
            return $arr[$k];
        }

        return $pivotIdx < $k
            ? $select($pivotIdx + 1, $high)
            : $select($low, $pivotIdx - 1);
    };

    return $select(0, count($arr) - 1);
}

// [3, 2, 1, 5, 6, 4], k=2 -> 2 (second smallest)
**Сложность Quick Select:** O(n) в среднем, O(n²) в худшем.

Оптимизации

<?php
declare(strict_types=1);

function optimizedQuickSort(array &$arr, int $low = 0, ?int $high = null): void
{
    if ($high === null) {
        $high = count($arr) - 1;
    }

    while ($low < $high) {
        // For small arrays — insertion sort
        if ($high - $low < 16) {
            insertionSortRange($arr, $low, $high);
            return;
        }

        // Randomized pivot
        $randIdx = random_int($low, $high);
        [$arr[$randIdx], $arr[$high]] = [$arr[$high], $arr[$randIdx]];

        $pivotIdx = partition($arr, $low, $high);

        // Tail call optimization: recurse on smaller part
        if ($pivotIdx - $low < $high - $pivotIdx) {
            optimizedQuickSort($arr, $low, $pivotIdx - 1);
            $low = $pivotIdx + 1;
        } else {
            optimizedQuickSort($arr, $pivotIdx + 1, $high);
            $high = $pivotIdx - 1;
        }
    }
}
## Quick Sort vs Merge Sort
Свойство Quick Sort Merge Sort
Среднее O(n log n) O(n log n)
Худшее O(n²) O(n log n)
Память O(log n) O(n)
Стабильность Нет Да
Cache Отличный Хуже
На практике Обычно быстрее Гарантированный

Запомни: Quick Sort на практике быстрее Merge Sort благодаря лучшей cache locality и меньшему потреблению памяти. Рандомизированный pivot делает worst case крайне маловероятным. Quick Select — O(n) для поиска k-го элемента. Современные std sort (Go, C++) используют introsort: quick sort + heap sort fallback при деградации.

Итоги

  1. Partition: ключевая операция, размещает pivot на правильное место
  2. O(n log n) в среднем, O(n²) в худшем
  3. In-place, но нестабильна
  4. Randomized pivot = почти гарантированный O(n log n)
  5. Quick Select: k-й элемент за O(n)
  6. На практике быстрее merge sort (cache-friendly)

Проверь себя

Зачем в оптимизированном Quick Sort переключаться на Insertion Sort для маленьких подмассивов?

Что делает partition в Quick Sort?

Почему Quick Sort на практике обычно быстрее Merge Sort, несмотря на одинаковую среднюю сложность O(n log n)?

Какова средняя сложность Quick Select для поиска k-го наименьшего элемента?

Какой массив является ХУДШИМ случаем для Quick Sort с pivot = последний элемент (Lomuto partition)?

Связанные темы

Counting и Radix Sort

Связанная тема

Задача о рюкзаке

Связанная тема