Quicksort – warianty, Introsort, benchmark vs wbudowany sort()

W listopadzie 2018 pisałem o podstawowych algorytmach sortowania. Czas na Quicksort – jeden z najważniejszych algorytmów w historii informatyki, średnio O(n log n) i jeden z najszybszych w praktyce. Implementuję kilka wariantów w PHP, pokazuję gdzie Quicksort bije inne algorytmy i dlaczego wbudowany sort() PHP jest szybszy niż własna implementacja.

Quicksort – idea

Quicksort działa na zasadzie „dziel i zwyciężaj”. Wybiera element zwany pivotem, dzieli tablicę na dwie części (mniejsze od pivotu i większe), a potem rekurencyjnie sortuje obie części. Kluczowy element to wybór pivotu – od niego zależy efektywność algorytmu.

Implementacja podstawowa – pivot jako pierwszy element

<?php

declare(strict_types=1);

// Quicksort - wersja naiwna, pivot = pierwszy element
function quicksortBasic(array $arr): array
{
    if (count($arr) <= 1) {
        return $arr;
    }

    $pivot  = $arr[0];
    $left   = [];
    $right  = [];

    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] <= $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    return [...quicksortBasic($left), $pivot, ...quicksortBasic($right)];
}

$data   = [64, 34, 25, 12, 22, 11, 90, 43, 7, 88];
$sorted = quicksortBasic($data);
print_r($sorted); // [7, 11, 12, 22, 25, 34, 43, 64, 88, 90]

Problem z pivotem jako pierwszym elementem: gdy tablica jest już posortowana lub prawie posortowana, Quicksort degeneruje do O(n²) – za każdym razem pivot jest najmniejszym elementem i partycja jest nierówna (0 elementów po lewej, n-1 po prawej).

Quicksort z losowym pivotem

<?php

declare(strict_types=1);

// Losowy pivot - eliminuje worst case dla posortowanych tablic
function quicksortRandom(array $arr): array
{
    $n = count($arr);

    if ($n <= 1) {
        return $arr;
    }

    // Losowy pivot - unika O(n²) dla posortowanych danych
    $pivotIndex = random_int(0, $n - 1);
    $pivot      = $arr[$pivotIndex];

    $left   = [];
    $middle = []; // elementy równe pivotowi - Three-way partition
    $right  = [];

    foreach ($arr as $element) {
        if ($element < $pivot) {
            $left[] = $element;
        } elseif ($element > $pivot) {
            $right[] = $element;
        } else {
            $middle[] = $element; // duplikaty trafią tu
        }
    }

    return [...quicksortRandom($left), ...$middle, ...quicksortRandom($right)];
}

// Three-way partition (Dutch National Flag) - wydajny przy wielu duplikatach
$dataWithDupes = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9];
$sorted = quicksortRandom($dataWithDupes);
print_r($sorted); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9, 9]

Quicksort in-place – wariant bez tworzenia nowych tablic

Wersje wyżej tworzą nowe tablice przy każdym podziale – zużycie pamięci O(n log n). Wariant in-place sortuje w miejscu przez wymianę elementów, zużycie pamięci O(log n):

<?php

declare(strict_types=1);

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

    if ($low >= $high) {
        return;
    }

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

    quicksortInPlace($arr, $low, $pivotIndex - 1);
    quicksortInPlace($arr, $pivotIndex + 1, $high);
}

function partition(array &$arr, int $low, int $high): int
{
    // Median-of-three pivot - lepsza wydajność niż losowy dla typowych danych
    $mid = intdiv($low + $high, 2);

    // Wybierz medianę z pierwszego, środkowego i ostatniego elementu
    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]];
    }

    // Przenieś pivot na pozycję high-1
    $pivot = $arr[$mid];
    [$arr[$mid], $arr[$high - 1]] = [$arr[$high - 1], $arr[$mid]];

    $i = $low;
    $j = $high - 1;

    while (true) {
        while ($arr[++$i] < $pivot);
        while ($arr[--$j] > $pivot);

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

        [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
    }

    // Przywróć pivot na właściwe miejsce
    [$arr[$i], $arr[$high - 1]] = [$arr[$high - 1], $arr[$i]];

    return $i;
}

$data = [64, 34, 25, 12, 22, 11, 90, 43, 7, 88, 55, 31];
quicksortInPlace($data);
print_r($data);

Introsort – hybryda Quicksort + Heapsort + Insertion Sort

W praktyce najlepsze implementacje sortowania to hybrydy. Introsort (używany przez C++ std::sort i PHP wewnętrznie) łączy trzy algorytmy:

<?php

declare(strict_types=1);

// Uproszczona implementacja Introsort w PHP
// Quicksort + Insertion Sort dla małych tablic (jak robi to PHP wewnętrznie)
function introsort(array $arr): array
{
    $n = count($arr);

    if ($n <= 16) {
        // Insertion Sort dla małych tablic - mniej narzutu niż rekurencja
        return insertionSort($arr);
    }

    // Losowy pivot + Three-way partition
    $pivotIndex = random_int(0, $n - 1);
    $pivot      = $arr[$pivotIndex];

    $left   = array_filter(array_values($arr), fn($x) => $x < $pivot);
    $middle = array_filter(array_values($arr), fn($x) => $x === $pivot);
    $right  = array_filter(array_values($arr), fn($x) => $x > $pivot);

    return [...introsort(array_values($left)), ...array_values($middle), ...introsort(array_values($right))];
}

function insertionSort(array $arr): array
{
    $n = count($arr);

    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j   = $i - 1;

        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }

        $arr[$j + 1] = $key;
    }

    return $arr;
}

Benchmark – własna implementacja vs wbudowany sort()

<?php

declare(strict_types=1);

function benchmark(string $name, callable $fn, array $data): void
{
    $start  = microtime(true);
    $result = $fn($data);
    $time   = (microtime(true) - $start) * 1000;

    echo sprintf("%-30s %8.3f ms (%d elementów)\n", $name, $time, count($result));
}

$sizes = [1000, 10000, 100000];

foreach ($sizes as $size) {
    $data = array_map(fn() => random_int(1, $size * 10), range(1, $size));

    echo "\n=== {$size} elementów ===\n";

    benchmark('Quicksort (losowy pivot)', fn($d) => quicksortRandom($d), $data);
    benchmark('Introsort (hybryda)',      fn($d) => introsort($d),        $data);
    benchmark('PHP sort() (C, Timsort)', function($d) { sort($d); return $d; }, $data);
    benchmark('PHP usort() (callable)',  function($d) { usort($d, fn($a,$b) => $a<=>$b); return $d; }, $data);
}

Typowe wyniki dla 100 000 elementów:

Kiedy pisać własny Quicksort?

W praktyce PHP nigdy nie piszesz własnego Quicksort do sortowania danych – sort(), usort() i uasort() są napisane w C i zawsze wygrają. Implementacja od zera ma sens w trzech sytuacjach: nauka algorytmów, rozmowa rekrutacyjna albo przeniesienie logiki sortowania do innego środowiska (np. JavaScript, Python) gdzie rozumiesz mechanizm bo pisałeś go w PHP.

Podsumowanie

Quicksort to algorytm który warto rozumieć nawet jeśli nigdy nie napiszesz go w produkcyjnym PHP. Wybór pivotu decyduje o wszystkim – naiwny pierwszy element degraduje do O(n²) na posortowanych danych, losowy pivot lub median-of-three eliminują ten problem. Wbudowany sort() PHP używa Timsort (hybryda Merge Sort i Insertion Sort) – jest szybszy od każdej implementacji PHP i to jest właśnie punkt: znajomość algorytmów pozwala wybrać właściwe narzędzie, niekoniecznie implementować je od zera.