Quicksort

Quicksort v akci na několika náhodných číslech. Horizontální hodnoty jsou pivoty

Quicksort (česky „rychlé řazení“) je jeden z nejrychlejších běžných algoritmů řazení založených na porovnávání prvků. Jeho průměrná časová složitost je pro algoritmy této skupiny nejlepší možná (O(N log₂ N)), v nejhorším případě (kterému se ale v praxi jde obvykle vyhnout) je však jeho časová náročnost O(N²). Další výhodou algoritmu je jeho jednoduchost.

Algoritmus

Algoritmus v akci na několika náhodných číslech. Zvýrazněné hodnoty jsou pivoty, modré jsou menší nebo stejné a červené jsou větší

Základní myšlenkou quicksortu je rozdělení řazené posloupnosti čísel na dvě přibližně stejné části (quicksort patří mezi algoritmy typu rozděl a panuj). V jedné části jsou čísla větší a ve druhé menší, než nějaká zvolená hodnota (nazývaná pivot – anglicky „střed otáčení“). Pokud je tato hodnota zvolena dobře, jsou obě části přibližně stejně velké. Pokud budou obě části samostatně seřazeny, je seřazené i celé pole. Obě části se pak rekurzivně řadí stejným postupem.

Volba pivotu

Největším problémem celého algoritmu je volba pivotu. Pokud se daří volit číslo blízké mediánu řazené části pole, je algoritmus skutečně velmi rychlý. V opačném případě se jeho časová složitost blíží O(N²). Přirozenou metodou na získání pivotu se pak jeví volit za pivot medián. Hledání mediánu (a obecně k-tého prvku) v posloupnosti běží v lineárním čase vzhledem k počtu prvků, tím dostaneme složitost O(N log₂ N) v nejhorším případě. Nicméně tato implementace není příliš rychlá z důvodu vysokých konstant schovaných v O notaci. Proto existuje velké množství alternativních způsobů, které se snaží efektivně vybrat pivot co nejbližší mediánu. Zde je seznam některých metod:

• První prvek – popřípadě kterákoli jiná fixní pozice. (Fixní volba prvního prvku je velmi nevýhodná na částečně seřazených množinách.)
• Náhodný prvek – často používaná metoda. Lze dokázat, že pokud je pozice pivotu skutečně náhodná, algoritmus poběží v O(N log N). Skutečně náhodná čísla generují ale pouze hardwarové generátory, které nemusí dodávat data dostatečně rychle. V praxi se používá spíše pseudonáhodný výběr.
• Metoda mediánu tří – případně pěti či libovolné jiné konstanty. Pomocí pseudonáhodného algoritmu (používají se i fixní pozice, typicky první, prostřední a poslední) se vybere několik prvků z množiny, ze kterých se použitím některého primitivního řadicího algoritmu najde medián a ten je zvolen za pivot.

Průměrná časová náročnost Quicksortu pro náhodná data je řádu O(N log₂ N). Testy ukazují, že na pseudonáhodných datech je nejrychlejší ze všech obecných řadicích algoritmů (tedy i rychlejší než Heapsort a Mergesort, které jsou formálně rychlejší). Praktické zkušenosti prvenství Quicksortu rovněž potvrzují. Rychlost Quicksortu však není zaručena pro všechny vstupy. Maximální časová náročnost O(N²) a použití rekurze Quicksort diskvalifikují v kritických aplikacích.

Kód algoritmu v jazyce Pascal

procedure quicksort(l, r: integer);
var 
    i, j, pivot, pom: integer;
begin
    i := l; j := r;
    pivot := akt[(l + r) div 2];
    repeat
        while (i < r) and (akt[i] < pivot) do i := i + 1;
        while (j > l) and (pivot < akt[j]) do j := j - 1;
        if i <= j then 
        begin
            pom := akt[i];
            akt[i] := akt[j];
            akt[j] := pom;
            i := i + 1;
            j := j - 1;
       end;
    until i > j;
    if j > l then quicksort(l, j);
    if i < r then quicksort(i, r)
end;

Kód algoritmu v jazyce C

void quicksort(int array[], int left_begin, int right_begin)
{
    int pivot = array[(left_begin + right_begin) / 2];
    int left_index, right_index, pom;
    left_index = left_begin;
    right_index = right_begin;
    do {
        while (array[left_index] < pivot && left_index < right_begin) left_index++;
        while (array[right_index] > pivot && right_index > left_begin) right_index--;
 
        if (left_index <= right_index) {
            pom = array[left_index];
            array[left_index++] = array[right_index];
            array[right_index--] = pom;
        }
    } while (left_index < right_index);
 
    if (right_index > left_begin) quicksort(array, left_begin, right_index);
    if (left_index < right_begin) quicksort(array, left_index, right_begin);
}

Vlastnosti a využití

Jak již bylo zmíněno, tento algoritmus je ve většině běžných případů nejrychlejší, což může být při řazení rozsáhlých posloupností hlavním požadavkem. Obecně je nestabilní. Může být upraven tak, aby byl stabilní, avšak na to je potřeba dodatečná paměť.

Rychlost výpočtu je většinou vynikající, avšak tento algoritmus vyžaduje více než jiné pečlivou implementaci. Zde uvedená základní rekurzivní verze algoritmu (tj. bez sofistikovanějšího výběru pivotu a bez modifikace proti přetečení zásobníku), může být pro nasazení v praxi naprosto nevhodná. Základní quicksort je nejpomaleší při třídění již setříděných nebo převážně setříděných polí. Vzhledem k tomu, že nejde o stabilní řadicí algoritmus, a vzhledem k nutnosti obcházet jeho nedostatky mohou být knihovní funkce pro quicksort na různých systémech a v různých knihovnách implementovány různým způsobem. To znamená, že při zavolání knihovní funkce nebude pole setříděno vždy stejně, což je potenciálním zdrojem problémů s přenositelností software.

Navíc na slabším hardware (například u jednoduchých vestavěných systémů) nebo při řazení velkých polí může prostoduchá implementace quicksortu vést dokonce i k přeplnění zásobníku a pádu programu. Je třeba si uvědomit, že zde uvedený algoritmus pouze demonstruje funkční princip quicksortu. Jde o rekurzivní algoritmus a každé rekurzivní volání spotřebovává paměť zásobníku, která bývá u vestavěných procesorů často omezená. Tento problém se nemusí při ladění projevit, protože množství spotřebované paměti závisí na řazených datech.

Navzdory výše zmíněným problémům jde v drtivé většině případů o nejrychlejší známý univerzální algoritmus pro řazení polí v operační paměti počítače. Ne však nejsnadněji použitelný.

Externí odkazy

• Vícerozměrný quicksort v Javě
• Tutorial Quicksortu s průběhem, diagramy a zdrojovými kódy v Javě (Anglicky)

Literatura

Wirth, N.: Algoritmy a štruktúry údajov, Alfa, Bratislava, 1989