Quicksort

Quicksort je velmi rychlý nestabilní řadící algoritmus na principu Divide et Impera (rozděl a panuj) s asymptotickou složitostí $O(n^{2})$ a s očekávanou složitostí $O(n \\cdot \\log{n})$ . Algoritmus vymyslel v roce 1962 Sir Charles Antony Richard Hoare.

Princip

Quicksort - pivotem je první prvek

Zvolme v zadaném poli libovolný prvek a říkejme mu pivot. Nyní můžeme pole přeházet tak, aby na jedné straně byly prvky větší než pivot, na druhé menší než pivot a pivot samotný byl umístěn přesně mezi těmito částmi. Tento postup můžeme zopakovat pro obě rozdělené části (bez pivota, ten je již umístěn na správném místě). Proceduru opakujeme tak dlouho, dokud nenarazíme na všechny triviálně řešitelné podproblémy (pole velikosti 1). V tento okamžik je celé pole seřazeno od nejvyššího prvku.

Výkonnost algoritmu

Výkonnost quicksortu je dána především volbou dobrého pivota. Pokud jej volíme ideálně, tak dojde při každém rekurzívním volání k rozpůlení pole a vystačíme si tedy s $\\log_{2}{n}$ voláními, v nichž popřehazujeme až prvků. Složitost tohoto případu je proto $O(n\\cdot \\log_{2}{n})$ .

Na druhou stranu, pokud nemáme štěstí a pivota volíme špatně (tj. nejvyšší nebo nejnižší možný prvek), tak nedojde k žádnému dělení podproblému, pouze dojde vždy k zařazení pivota na správné místo. Při každém z volání procedury spotřebujeme až operací na ověření pořadí, případně na přesun prvků. Složitost tohoto patologického případu je proto $O(n^{2})$ .

Výkon na malých datech

Za povšimnutí stojí, že při menších velikostech řazeného pole je quicksort poměrně pomalý, protože velmi pravděpodobně nedojde rozdělení pole na ideální poloviny. Tuto situaci si můžeme ukázat na dělení podproblému $[4,\\;5,\\;6]$ (viz obrázek), ve které volíme za pivota číslo 4, ale úloha se zkrátí jen o 1.

Z tohoto důvodu se quicksort používá zejména při řazení velkých polí. Dílčí malé podproblémy (cca. $n \\leq 10$ ) je vhodné řešit pomocí jiných algoritmů - například insertion sortu nebo Shell sortu, které jsou při malých velikostech polí výrazně rychlejší.

Volba pivota

Pro volbu pivota existuje mnoho strategií. Jednou z nich je volba fixního prvku (tj. prvního, posledního...). Tento postup je problematický na částečně uspořádaných polích, případně na polích s nějakou strukturou, kde nedochází k optimálnímu dělení problému a složitost narůstá až k $n^{2}$ . Tomuto chování se lze vyhnout volbou mediánu prvního, posledního a prostředního prvku řazeného úseku pole.

Druhou populární strategii je volba náhodného prvku. Zde je problémem již zajištění samotné náhodnosti volby, respektive opakující se vzory v chování generátoru čísel (v extrémním případě může strategie degradovat až k poněkud komplikovanější volbě fixního prvku). V praxi se ale ukazuje, že bohatě postačí i pseudonáhodné generátory.

Vizualizace

Kód

procedure quicksort(List values)
    if values.size <= 1 then
        return values
 
    pivot = náhodný prvek z values
 
    Rozděl seznam values do 3 seznamů
        seznam1 = { prvky větší než pivot }
        seznam2 = { pivot }
        seznam3 = { prvky menší než pivot }
     
    return quicksort(seznam1) + seznam2 + quicksort(seznam3)

/**
 * Quicksort - rychle razeni (pivotem je prvni prvek), radi od nejvyssiho prvku
 * @param array pole k serazeni
 * @param left index prvniho prvku, na ktery muzeme sahnout (leva mez (vcetne))
 * @param right index prvniho prvku, na ktery nemuzeme sahnout (prava mez (bez))
 */
public static void quicksort(int[] array, int left, int right){
    if(left < right){ 
        int boundary = left;
        for(int i = left + 1; i < right; i++){ 
            if(array[i] > array[left]){ 
                swap(array, i, ++boundary);
            }
        }
        swap(array, left, boundary);
        quicksort(array, left, boundary);
        quicksort(array, boundary + 1, right);
    }     
}
 
/**
 * Prohodi prvky v zadanem poli
 * @param array pole
 * @param left prvek 1
 * @param right prvek 2
 */
private static void swap(int[] array, int left, int right){
    int tmp = array[right]; 
    array[right] = array[left];
    array[left] = tmp;
}

/**
 * Quicksort - rychle razeni (pivotem je prvni prvek), radi od nejvyssiho prvku
 * @param array pole k serazeni
 * @param left index prvniho prvku, na ktery muzeme sahnout (leva mez (vcetne))
 * @param right index prvniho prvku, na ktery nemuzeme sahnout (prava mez (bez))
 */
void quicksort(int array[], int left, int right){
    if(left < right){ 
        int boundary = left;
        for(int i = left + 1; i < right; i++){ 
            if(array[i] > array[left]){ 
                swap(array, i, ++boundary);
            }
        }
        swap(array, left, boundary);
        quicksort(array, left, boundary);
        quicksort(array, boundary + 1, right);
    }     
}
 
/**
 * Prohodi prvky v zadanem poli
 * @param array pole
 * @param left prvek 1
 * @param right prvek 2
 */
void swap(int array[], int left, int right){
    int tmp = array[right]; 
    array[right] = array[left];
    array[left] = tmp;         
}

/**
 * Quicksort - rychle razeni (pivotem je prvni prvek), radi od nejvyssiho prvku
 * @param array pole k serazeni
 * @param left index prvniho prvku, na ktery muzeme sahnout (leva mez (vcetne))
 * @param right index prvniho prvku, na ktery nemuzeme sahnout (prava mez (bez))
 */
 public static void Quicksort(int[] array, int left, int right)
 {
     if (left < right)
     {
         int boundary = left;
         for (int i = left + 1; i < right; i++)
         {
             if (array[i] > array[left])
             {
                 Swap(array, i, ++boundary);
             }
         }
         Swap(array, left, boundary);
         Quicksort(array, left, boundary);
         Quicksort(array, boundary + 1, right);
     }
 }
 
/**
 * Prohodi prvky v zadanem poli
 * @param array pole
 * @param left prvek 1
 * @param right prvek 2
 */
 private static void Swap(int[] array, int left, int right)
 {
     int tmp = array[right];
     array[right] = array[left];
     array[left] = tmp;
 }

Princip

Výkonnost algoritmu

Výkon na malých datech

Volba pivota

Vizualizace

Kód

Doporučujeme