Quicksort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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(N2). Další výhodou algoritmu je jeho jednoduchost.

Objevil jej Sir Charles Antony Richard Hoare v roce 1962.

Algoritmus[editovat | editovat zdroj]

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, což ale neznamená, že implementace musí taky použít rekurzi.

Volba pivotu[editovat | editovat zdroj]

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 doba běhu prodlužuje a v extrémním případě je časová složitost O(N2). 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) quicksortu 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. Průměr přes každá data je O(N log N), přičemž zde se průměr bere přes všechny možné volby pivotů (rozděleno rovnoměrně). Nejhorší případ zůstává O(N2), protože pro každá data může náhoda nebo Velmi Inteligentní Protivník vybírat soustavně nevhodného pivota, např. druhé největší číslo. V praxi většinou není dostupný generátor skutečně náhodných čísel, proto se používá pseudonáhodný výběr.
  • Metoda mediánu tří – případně pěti či jiného počtu prvků. Pomocí pseudonáhodného algoritmu (také se používají fixní pozice, typicky první, prostřední a poslední) se vybere několik prvků z množiny, ze kterých se vybere medián a ten je použit jako pivot.

Pokud by bylo zaručeno, že pivota volíme vždy z 98 % prvků uprostřed a ne z 1 % na některé straně, algoritmus by stále měl nejhorší asymptotickou složitost O(N log N), byť s poněkud větší konstantou v O-notaci.

Praktické zkušenosti a testy ukazují, že na pseudonáhodných nebo reálných datech je Quicksort nejrychlejší ze všech obecných řadicích algoritmů (tedy i rychlejší než Heapsort a Mergesort, které jsou formálně rychlejší). Rychlost Quicksortu však není zaručena pro všechny vstupy. Maximální časová náročnost O(N2) Quicksort diskvalifikují pro kritické aplikace.

Kód algoritmu v jazyce Pascal[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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);
}

Omezení hloubky rekurze[editovat | editovat zdroj]

Tento algoritmus vyžaduje více než jiné pečlivou implementaci. Zde uvedená základní rekurzivní verze algoritmu může být pro nasazení v praxi nevhodná, výše 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. Ve výše zmiňovaném nejhorším případě (opakovaná volba nejmenšího prvku za pivota) by spotřeba paměti rostla lineárně, což by mohlo dokonce způsobit pád aplikace. Problém s hlubokou rekurzí se nemusí při ladění projevit, protože hloubka rekurze závisí na řazených datech. Avšak zabránit hluboké rekurzi je možné. Po pivotizaci lze

  • nejdříve řadit menší část za použití rekurze
  • poté řadit větší část sekvence již nerekurzivně

Tím je zaručeno, že hloubka rekurze neroste nikdy lineárně, je nejvýše log2 N.

Nerekurzivní verze algoritmu[editovat | editovat zdroj]

Implementace se, například kvůli rychlosti, může vyhnout použití rekurze a ošetřuje si zásobník sama. Také průmyslový standard MISRA C používaný pro vestavěné systémy použití rekurze zakazuje. Na zásobník se ukládají hranice ještě nezpracovaných částí. Důležitý trik pro zmenšení zásobníku je na zásobník uložit (pouze) tu větší část a dále, tedy dřív, zpracovávat vždy menší z rozdělených části. To zaručí, že stačí zásobník velikosti log2 N, tj. například pro miliardu prvků stačí hloubka 30 položek. Bez této optimalizace by byla paměť potřebná pro zásobník až lineární. Jedná se o postup ekvivalentní zabránění hluboké rekurze.

Shrnutí[editovat | editovat zdroj]

  • rychlost výpočtu je vynikající O(N log N), avšak při nejhorším případě časová náročnost roste na O(N2)
  • při správné implementaci prakticky nepotřebuje dodatečnou paměť, řadí prvky přímo v poli
  • jde o nestabilní algoritmus, způsob volby pivota může mít vliv na výsledek řazení
  • vzhledem k nejhoršímu případu nemusí být vždy vhodný pro vestavěné systémy běžící na slabším hardware
  • v průměru jde o nejrychlejší známý univerzální algoritmus pro řazení polí v operační paměti počítače
  • k omezení pravděpodobnosti nejhoršího případu slouží různé postupy volby pivota
  • jde o rekurzivní algoritmus, ale hloubku rekurze lze omezit; s použitím zásobníku jej lze algoritmus převést na nerekurzivní
  • nerekurzviní verze algoritmu je efektivnější (je rychleší a spotřebuje méně paměti)
  • bývá implementován v systémových knihovnách (např. v C-jazku funkce qsort z knihovny stdlib.h)

Externí odkazy[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

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