Quicksort może być świetny przeciętnie i fatalny w najgorszym przypadku
Quicksort wybiera pivot, dzieli dane na elementy mniejsze i większe od niego, a potem rekurencyjnie sortuje powstałe części. Gdy podziały są w miarę zrównoważone, otrzymujemy oczekiwany czas rzędu n log n. Jeśli jednak pivot konsekwentnie trafia blisko skrajnej wartości, kolejne podproblemy mają rozmiary n-1, n-2, n-3… i praca rośnie do rzędu n². Co ciekawe, randomizacja może uniezależnić oczekiwaną wydajność od wrogiego uporządkowania wejścia: losowy pivot nadal ma możliwy zły przebieg, lecz jego oczekiwany czas jest O(n log n). To klasyczny przykład różnicy między gwarancją najgorszego przypadku a zachowaniem oczekiwanym.
Cały los algorytmu zależy od podziału
Sercem quicksortu jest partycjonowanie. Wybieramy element nazywany pivotem, ustawiamy elementy po odpowiednich stronach względem niego i otrzymujemy dwa mniejsze problemy. Idealnie pivot jest blisko mediany. Wtedy problem o rozmiarze n rozpada się mniej więcej na dwie połowy, każda z nich znów na połowy, a liczba poziomów rekursji rośnie logarytmicznie. Na każdym poziomie trzeba łącznie przetworzyć około n elementów, stąd charakterystyczne O(n log n).
Ale jeśli każdy pivot okazuje się najmniejszym albo największym elementem bieżącego fragmentu, prawie nic nie dzielimy. Zamiast dwóch połówek dostajemy część pustą i część o rozmiarze n-1. Potem n-2 i tak dalej. Materiały University of Michigan pokazują klasyczny przykład posortowanej tablicy połączonej z naiwnym wyborem pierwszego elementu na pivot: taki przypadek prowadzi do O(n²).
To nie sprzeczność: „szybki” i „kwadratowy” mogą być prawdziwe jednocześnie
Ocena algorytmu nie jest jedną liczbą. Możemy pytać o najgorszy przypadek, średni przypadek, oczekiwany czas po losowych decyzjach albo zachowanie na typowych danych. Quicksort jest doskonałym przykładem, bo różnice są wyraźne. Deterministyczna wersja z niefortunną regułą wyboru pivota może mieć łatwe do skonstruowania wejście kwadratowe. To nie unieważnia faktu, że przy dobrych podziałach quicksort zachowuje się bardzo dobrze.
W praktyce implementacje sortowania często stosują dodatkowe zabezpieczenia, hybrydy lub strategie wyboru pivota właśnie po to, aby nie polegać na najprostszym wariancie z podręcznika. Ważna jest więc precyzja: stwierdzenie „quicksort ma złożoność O(n log n)” bez dopowiedzenia, o jakim rodzaju granicy mówimy, jest uproszczeniem.
Losowość jako ochrona przed strukturą wejścia
MIT w kursie poświęconym algorytmom randomizowanym omawia pomysł losowego wyboru pivota lub wcześniejszego losowego przemieszania danych. Dzięki temu porządek dostarczony przez użytkownika przestaje determinować, czy algorytm stale wybiera fatalne pivoty. Dla randomizowanego quicksortu można wykazać oczekiwany czas Θ(n log n) dla dowolnej ustalonej tablicy wejściowej — źródłem losowości jest algorytm, nie założenie, że dane „same są losowe”.
Nie jest to jednak gwarancja, że pojedyncze uruchomienie nigdy nie będzie złe. Sekwencja wyjątkowo pechowych losowych wyborów nadal jest możliwa. Zmienia się coś innego: przeciwnik nie może łatwo przygotować jednego zwykłego układu danych, który deterministycznie wywoła najgorszy przebieg, jeśli nie kontroluje losowych decyzji algorytmu.
Dlaczego quicksort jest tak dobrym przykładem myślenia algorytmicznego
Quicksort pokazuje, że warto rozdzielać trzy pytania. Po pierwsze: jaki jest najgorszy teoretyczny koszt? Po drugie: co dzieje się przeciętnie lub w wartości oczekiwanej? Po trzecie: jakie właściwości sprzętu i implementacji decydują o szybkości w rzeczywistym programie? Dwa algorytmy o tej samej asymptotycznej klasie mogą mieć różne stałe, użycie pamięci i lokalność odwołań.
Dlatego analiza O nie jest rankingiem „który program jest zawsze szybszy”. Jest sposobem opisu skalowania. Quicksort może być bardzo atrakcyjny praktycznie, a jednocześnie nie spełniać wymogu gwarantowanego O(n log n) w swojej podstawowej wersji. W systemie z twardym limitem czasu najgorszy przypadek może być ważniejszy niż świetna średnia. W innym zastosowaniu oczekiwana wydajność i mały narzut mogą mieć większe znaczenie.
Losowy pivot przenosi niepewność z danych do własnych decyzji algorytmu
W deterministycznej wersji wybierającej zawsze pierwszy element istnieją łatwe do skonstruowania dane powodujące ciąg skrajnie nierównych podziałów. Randomizowany quicksort odwraca sytuację: dla dowolnego ustalonego wejścia pivot jest wybierany losowo. Analiza MIT podkreśla, że oczekiwane O(n log n) nie wymaga założenia, iż sama tablica została losowo potasowana. To ważna różnica między analizą średniego przypadku a algorytmem randomizowanym. W pierwszej losowość przypisujemy światu zewnętrznemu i zakładamy rozkład danych. W drugiej program sam wprowadza losową decyzję. Dzięki temu nawet bardzo regularne, posortowane lub celowo skonstruowane wejście nie determinuje już jednej patologicznej sekwencji pivotów. Zły przebieg nadal jest możliwy, lecz nie jest na stałe zakodowany w strukturze wejścia.