Significations et usages de Quicksort

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.

  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. 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 řadicího algoritmu najde medián a ten je zvolen za pivot.

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 řadicí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.

  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
      if i < j then
      begin
        pom := akt[i];
        akt[i] := akt[j];
        akt[j] := pom;
      end;
      if i < r then i := i + 1;
      if j > l then 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;
                if (left_index < right_begin)
                    left_index++;
                if (right_index > left_begin)
                    right_index--;
            }
        } 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);
    }

  Kód algoritmu v jazyce Haskell

    quicksort :: (Ord a) => [a] -> [a]
    quicksort [] = []
    quicksort [x] = [x]
    quicksort (x:xs) = quicksort(filter (<x) xs) ++ x:quicksort(filter (>=x) xs)

  Výhody a nevýhody

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 systému. 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ádní 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