Mid📖Теория5 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)

PHPGo
<?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;
}

func quickSort(arr []int, low, high int) {
    if low < high {
        pivotIdx := partition(arr, low, high)
        quickSort(arr, low, pivotIdx-1)
        quickSort(arr, pivotIdx+1, high)
    }
}

func partition(arr []int, low, high int) 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 (более эффективная)

PHPGo
<?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]];
    }
}

func hoarePartition(arr []int, low, high int) int {
    pivot := arr[low]
    i := low - 1
    j := high + 1

    for {
        for {
            i++
            if arr[i] >= pivot {
                break
            }
        }

        for {
            j--
            if arr[j] <= pivot {
                break
            }
        }

        if i >= j {
            return j
        }

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

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

PHPGo
<?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];
}

import "math/rand"

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

// 2. Random — good on average
randIdx := rand.Intn(high-low+1) + low
arr[randIdx], arr[high] = arr[high], arr[randIdx]
pivot = arr[high]

// 3. Median of three — good compromise
func medianOfThree(arr []int, low, high int) int {
    mid := (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-го наименьшего элемента:

PHPGo
<?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)

// Find k-th smallest element (1-indexed)
func quickSelect(arr []int, k int) int {
    k-- // 0-indexed

    var sel func(low, high int) int
    sel = func(low, high int) int {
        if low == high {
            return arr[low]
        }

        pivotIdx := partition(arr, low, high)

        if pivotIdx == k {
            return arr[k]
        }

        if pivotIdx < k {
            return sel(pivotIdx+1, high)
        }
        return sel(low, pivotIdx-1)
    }

    return sel(0, len(arr)-1)
}

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

Оптимизации

PHPGo
<?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;
        }
    }
}

func optimizedQuickSort(arr []int, low, high int) {
    for low < high {
        // For small arrays — insertion sort
        if high-low < 16 {
            insertionSortRange(arr, low, high)
            return
        }

        // Randomized pivot
        randIdx := rand.Intn(high-low+1) + low
        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

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

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

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