Řadící algoritmy #2: Quick Sort

Algoritmus Quick Sort je jedním z algoritmů, využívajících metodu Rozděl a Panuj (řeší úlohy tak, že si ji rozdělí na několik menších úloh, které řeší samostatně).

Již podle názvu je možné usoudit, že metoda řazení pomocí Quick Sort je velmi rychlá. Jedná se o jeden z nejrychlejších algoritmů, které jsou v dnešní době známé, od čehož se odvíjí velmi malá časová složitost.

Na začátku řazení se volí hodnota, která se nazývá Pivot. Pivot je počáteční „stav“, ze kterého se vychází. Pivot by měl být volen tak, aby se co nejvíce přibližoval mediánu (čím blíže mediánu se volí, tím je algoritmus rychlejší).

Pomocí pivotu řadíme celou strukturu řazených dat na dvě části. Část pravou a levnou, kdy jedna z částí je větší než pivot a druhá je menší než pivot. Tento postup neustále opakujeme a neustále volíme nový a nový pivot v jednotlivých částech a ty neustále rozřazujeme na menší a větší hodnoty, dle pravidel řazení (u číselných hodnot je rozřazována na hodnoty menší a větší). Postupně nám vzniká seřazená struktura dat.

Nejsložitější z celého algoritmu je právě volba pivotu, protože jeho volba ovlivňuje rychlost celého algoritmu. Touto problematikou se zabývá spousta různých řešení a alternativ tohoto algoritmu, se kterými se můžete setkat na internetu. V praxi se používá několik základních způsobů:

první prvek zpracovávané skupiny souboru dat
poslední prvek zpracovávané skupiny souboru dat
prvek uprostřed zpracovávané skupiny souboru dat
náhodný prvek z aktuálně zpracovávané části dat
průměr všech hodnot v celé části souboru dat (medián)

Program v Javě by mohl vypadat například takto:

function QuickSort(int[] InArray, int left, int right);
    //ulozime si hodoty lefe a prave pozice, abychom je mohli menit
    int i = left, j = right;
    
    //najdeme si Pivot
    //Pro pivot volime vzdy prvni hodnotu
    int x = InArray[ left ];
    //v cylku projdeme celou cast, ktera je omezena hodnotami left a right
    do{
        //postupujeme z leva doprava 
        while( InArray[ i ] < x )
            i++; 
        //postupujeme z prava do leva
        while( InArray[ j ] > x ) 
            j--;
        //pokud je leva hodnota mensi nez prava
        if( i <= j )
        {
            //prohodime hodnoty
            int h = InArray[ i ]; 
            InArray[ i ] = InArray[ j ]; 
            InArray[ j ] = h;
            //posuneme souradnice
            i++; 
            j--;
        }
    }while( i <= j );
    
    //nakonec radime jednotlive casti
    if( left < j ) GoQuickSort( InArray, left, j );
    if( i < right ) GoQuickSort( InArray, i, right );
    //vracime vysledek
    return InArray;
}

function QuickSort(int[] InArray, int left, int right);

//ulozime si hodoty lefe a prave pozice, abychom je mohli menit

int i = left, j = right;

//najdeme si Pivot

//Pro pivot volime vzdy prvni hodnotu

int x = InArray[ left ];

//v cylku projdeme celou cast, ktera je omezena hodnotami left a right

do{

//postupujeme z leva doprava

while( InArray[ i ] < x )

i++;

//postupujeme z prava do leva

while( InArray[ j ] > x )

j--;

//pokud je leva hodnota mensi nez prava

if( i <= j )

{

//prohodime hodnoty

int h = InArray[ i ];

InArray[ i ] = InArray[ j ];

InArray[ j ] = h;

//posuneme souradnice

i++;

j--;

}

}while( i <= j );

//nakonec radime jednotlive casti

if( left < j ) GoQuickSort( InArray, left, j );

if( i < right ) GoQuickSort( InArray, i, right );

//vracime vysledek

return InArray;

}

Program rekurzivně řadí jednotlivé části, které rozděluje pivotem. Pivot je v programu volen jako levý prvek v poli čísel. Samozřejmě je možné pro volbu pivotu volit jakýkoli prvek a výsledek programu bude stejný.

Stabilní: ne
Přirozený: Ano
Minimální časová složitost: O(n log n)
Průměrná časová složitost: O(n log n)
Maximální časová složitost: O(n^2)

Volba pivotu

Jak jsem napsal, nejdůležitější na celém algoritmu je zjištění, nebo výpočet, pivotu. Pivot by měl být v ideálním případě medián, v praxi to ovšem vždy neplatí, protože výpočet mediánu může být při řazení různých struktur různě náročný a celý algoritmus se jeho výpočtem může zpomalovat.

Pro použití pivotu jsem uvedl několik základních způsobů, z nichž některé se nyní pokusím srovnat, porovnáním jejich časů, pro řazení.

Pro řazení bylo použito pole celých čísel o velikosti 6000 prvků. Toto pole bylo naplněno hodnotami:

hodnoty od 1 do n
náhodné hodnoty

Pro měření byl test spuštěn 100x, a výsledné časy a hodnoty jsou průměr těchto měření

Pole hodnot od 1 do N

Pole je vygenerováno jako posloupnost hodnot, začínajícími od 1 až do N, kdy N je celková velikost pole. Jedná se tedy o již seřazené pole:

Pivot je první prvek: 0.026675774 [s]
Pivot je poslední prvek: 0.02663383 [s]
Pivot je medián: 0.00027262974 [s]

Výsledek u takto seřazeného pole není ničím překvapivý. Naměřené hodnoty jsou samozřejmě nejmenší, když je pivot volen jako medián, Jelikož je pole již seřazeno a Pivot je volen správně..

Pole náhodných hodnot

Pole bylo vygenerováno jako soubor náhodných celých čísel o velikosti 1 až 6000, takže hodnoty v poli jsou podobné hodnotám z prvního měření, jenom přeházené:

Pivot je první prvek 0.024201134 [s]
Pivot je poslední prvek: 0.024809308 [s]
Pivot je medián: 0.0004194304 [s]

Ve výsledku tohoto měření, kde bylo použito pole náhodných čísel, je možné opět sledovat velké zrychlení v případě, že je Pivot volen jako medián. Celé pole je postupně řazeno a je vidět, že ani výpočet mediánu, který je v případě použití celých čísel jednoduchý, celý algoritmus nezpomalí.

Pole hodnot od N do 1

Pole bylo vygenerováno podobně jako v prvním případě, jenom s opačnou posloupností hodnot

Pivot je první prvek: 0.02717909 [s]
Pivot je poslední prvek: 0.026864517 [s]
Pivot je medián: 0.00029360127 [s]

Opět je vidět, že i když algoritmus počítá pivot, je tento způsob nejrychlejší a celé řazení se tím výrazně urychlí.

Závěrem

Řazení metodou QuickSort je jedním z nejrychlejších řadících algoritmů. Jeho rychlost však spočívá právě ve správné volbě Pivotu, o čemž jsme se přesvědčili v několika jednoduchých pokusech.

Pokud je pivot volen správně, je algoritmus velmi rychlý. Bohužel v případě, že je pivot volen špatně, může se zvětšit časová náročnost: O(n^2).