Quicksort

Z Wikipedie, otevřené encyklopedie

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

Quicksort neboli rychlé řazení je jeden z nejrychlejších známý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.

[editovat] 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). 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.

[editovat] Volba pivota

Největším problémem celého algoritmu je volba pivota. Pokud se daří volit číslo blízké mediánu řazené části pole, je algoritmus skutečně velmi rychlý. Pokud ne, je jeho paměťová i časová náročnost horší než u všech používaných řadicích algoritmů. Medián můžeme tedy vypočítat a zvolit jej za pivota. Toto je ale velmi neefektivní metoda, protože hledání mediánu běží v čase O(N). Výsledkem by byl velmi pomalý algoritmus. Proto existuje velké množství způsobů, které se snaží vybrat pivota co nejbližšího mediánu. Zde je seznam, pouze několika metod:

První prvek - popřípadě kterákoli jiná fixní pozice. Velmi nevýkonná především na částečně seřazených množinách.
Náhodný prvek - často používaná metoda. Jde 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 mnohdy stačí použít pseudonáhodný algoritmus.
Metoda mediánu tří - případně pěti, či libovolné jiné konstanty. Pomocí pseudonáhodného algoritmu (používají se i fixní pozice) se vybere X prvků z množiny, ze kterých se použitím některého primitivního řadícího algoritmu najde medián a ten je zvolen za pivota.

Přestože Quicksort nemá zaručenou časovou složitost O(N log N)), reálné aplikace a testy ukazují, že na pseudonáhodných datech je vůbec nejrychlejší ze všech obecných řadících algoritmů (tedy i rychlejší než Heapsort a Mergesort, které jsou formálně rychlejší). Maximální časová náročnost O(N²) ho však diskvalifikuje pro použití v kritických aplikacích.

[editovat] Kód algoritmu v jazyce Pascal

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