Quicksort

Z Wikipedie, otevřené encyklopedie

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

Quicksort neboli rychlé (rekurzivní) řazení do tříd 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ý. V opačném případě se jeho časová složitost blíží $O (N 2)$ . Přirozenou metodou na získání pivota 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 k počtu prvků, tím dostaneme složitost $O (N log 2 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 pivota co nejbližšího mediánu. Zde je seznam některých 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. 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 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;