Sortowanie w PHP – bubble sort, merge sort, usort() i operator <=>

Sortowanie to temat, który większość z nas „odhacza” na studiach i wraca do niego tylko przy rozmowach rekrutacyjnych. Tymczasem świadomość tego, jak działają algorytmy sortowania, pomaga podejmować lepsze decyzje nawet w codziennej pracy z PHP i bazami danych. Przechodzę przez kilka klasycznych podejść, piszę je w PHP i pokazuję gdzie ma to realne zastosowanie.

Bubble Sort – wolny, ale czytelny

Bubble sort to najprostszy algorytm do zrozumienia: porównuj sąsiadów, zamieniaj jeśli są w złej kolejności, powtarzaj. Złożoność: O(n²) – przy 1000 elementów to milion operacji porównania.

<?php

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

    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;

        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]]; // swap
                $swapped = true;
            }
        }

        // Optymalizacja: jeśli żaden swap nie nastąpił, tablica jest już posortowana
        if (!$swapped) {
            break;
        }
    }

    return $arr;
}

$data = [64, 34, 25, 12, 22, 11, 90];
print_r(bubbleSort($data));
// [11, 12, 22, 25, 34, 64, 90]

Merge Sort – dziel i zwyciężaj

Merge sort działa rekurencyjnie: dzieli tablicę na połowy, sortuje każdą z nich osobno, a potem scala. Złożoność: O(n log n) – znacznie lepsza, szczególnie przy dużych zbiorach danych. Wadą jest zużycie dodatkowej pamięci na podtablice.

<?php

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

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

    $mid   = (int) ($n / 2);
    $left  = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));

    return merge($left, $right);
}

function merge(array $left, array $right): array
{
    $result = [];
    $i = 0;
    $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }

    // Dołącz pozostałe elementy
    while ($i < count($left))  { $result[] = $left[$i++]; }
    while ($j < count($right)) { $result[] = $right[$j++]; }

    return $result;
}

$data = [38, 27, 43, 3, 9, 82, 10];
print_r(mergeSort($data));
// [3, 9, 10, 27, 38, 43, 82]

A może po prostu sort() z PHP?

PHP ma wbudowane funkcje sortowania, które w praktyce wygrają z Twoją własną implementacją – są napisane w C i zoptymalizowane pod PHP engine. Korzystają z wariantu Quicksort / Timsort, również O(n log n).

<?php

// Sortowanie prostej tablicy
$data = [3, 1, 4, 1, 5, 9, 2, 6];
sort($data);
print_r($data); // [1, 1, 2, 3, 4, 5, 6, 9]

// Sortowanie tablicy asocjacyjnej po wartości – zachowuje klucze
$prices = ['apple' => 1.5, 'banana' => 0.9, 'cherry' => 3.2];
asort($prices);
print_r($prices); // ['banana' => 0.9, 'apple' => 1.5, 'cherry' => 3.2]

// Sortowanie obiektów po polu – usort z callable
$products = [
    ['name' => 'Widget', 'price' => 29.99],
    ['name' => 'Gadget', 'price' => 9.99],
    ['name' => 'Doohickey', 'price' => 14.99],
];

usort($products, fn($a, $b) => $a['price'] <=> $b['price']);
// Gadget, Doohickey, Widget

Operator statku kosmicznego (<=>) – PHP 7.x

Operator <=> (spaceship operator, dostępny od PHP 7.0) zwraca -1, 0 lub 1 w zależności od relacji między dwoma wartościami. Idealny do usort():

<?php

// Zamiast pisać:
usort($arr, function($a, $b) {
    if ($a === $b) return 0;
    return ($a < $b) ? -1 : 1;
});

// Wystarczy:
usort($arr, fn($a, $b) => $a <=> $b);

// Sortowanie wielopoziomowe – najpierw po cenie, potem alfabetycznie
usort($products, function($a, $b) {
    return [$a['price'], $a['name']] <=> [$b['price'], $b['name']];
});

Kiedy to ma znaczenie w praktyce?

W codziennej pracy z PHP rzadko implementujesz Bubble Sort. Ale znajomość złożoności obliczeniowej pomaga unikać realnych błędów:

• Sortowanie 10 000 produktów w pętli zapytań SQL zamiast jednym ORDER BY - to O(n log n) w PHP zamiast indeksowanego sortowania w bazie
• Używanie in_array() w pętli na dużych tablicach - O(n²) zamiast przepisania na tablicę asocjacyjną i isset() - O(n)
• Nadmierne sortowanie kolekcji Magento w PHP, gdy można to zlecić Elasticsearch lub bazie danych

Podsumowanie

Znaj algorytmy - nie po to, żeby je implementować od zera w produkcyjnym kodzie, ale żeby rozumieć co robi za Ciebie framework, baza danych i sam PHP.