Quicksort je známý algoritmus řazení, který vymyslel pan Charles Antony Richard Hoare. Podle jeho autora se nazývá také někdy jako Hoaresort. Jedná se o jeden z nejpoužívanějších a nejrychlejších řadících algoritmů. Tento algoritmus se řadí mezi typy algoritmů rozděluj a panuj. Jádrem tohoto algoritmu je rekurze a rozdělování pole na části a jejich jednotlivé zpracování.
Časová složitost tohoto algoritmu je O(N log N) - to je opravdu výborné, ale v jistých případech se může asymptotická složitost vyhoupnout až na O(N²). Toho se dá ovšem vyvarovat. Vše závisí především na vhodně zvoleném pivotu.
Pivot je zvolená hodnota, které rozděluje pole na čísla menší a větší - oproti pivotu. Idelaní případ pivotu je, když by byl mediánem hodnot z prvků, které chceme seřadit. Obyčejně se však pivot volí z prvního čísla v poli. Také je ještě jeden způsob, kdy pivota můžeme zvolit pomocí náhodného čísla (v reálném programování mám na mysli pseudonáhodné číslo). V ukázkové implementaci v tomto článku budeme volit pivota z prvního čísla v poli.
Nyní již víme, co je to pivot, a že algoritmus používá rekurzi. Algoritmus tedy funguje tak, ze do nej vstupujeme s nějakým polem, prvním a posledním prvkem - z důvodů rekurze. Prvním krokem je, že seřadí pole v takovým způsobem, že nalevo vyrovná hodnoty menší než je pivot a vpravo hodnoty větší než pivot. Poté největší hodnotu z hodnot menších než pivot zamění právě s pivotem. Pro lepší pochopení určitě lépe poslouží následující obrázek, v kterém jsou tučně zvírazněny pivoty.
Z tohoto článku by už mělo být nějak tak jasné, jak algoritmus počítá (funguje). Přidávám ještě jednu demonstrativní animaci, která by mohla také pomoci k pochopení algoritmu Quicksort.
Tato animace určuje pivot jako pravý prvek z vybrané množiny. Označí ho vždy čevenou barvou.
Implementace do javy.
Způsobů jak implementovat Quicksort je spousta. Záleží především na výběru pivota. Exitují implementace, který využívají ryze základních funkcí a tříd jazyka, ale také existují způsoby zápisu, kde jsou použity například třídy Comparator, Random a jiné.
Algoritmus se skládá z dvou metod (také záleží na stylu implementace). První metodou je nahrada(). Tato metoda je pouze k tomu, že je volána metodou quicksort() k tomu, aby prohodila dané prvky v poli. Druhou metodou je právě quicksort(), která obsahuje rekurzi a volá sama sebe.
Metoda nahrada()
public static void nahrada(int[] pole, int start, int konec) {
int tmp = pole[konec];
pole[konec] = pole[start];
pole[start] = tmp;
}
Funkčnost této metody snad není třeba komentovat.
Metoda quicksort()
public static void quicksort(int pole[], int start, int konec) {
int s = start;
int k = konec;
if (konec - start >= 1) {
int pivot = pole[start];
while(k > s) {
while(pole[s] <= pivot && s <= konec && k > s) {
s++;
}
while(pole[k] > pivot && k >= start && k >= s) {
k--;
}
if(s < k) {
nahrada(pole, s, k);
}
}
nahrada(pole, k, start);
quicksort(pole, start, k - 1);
quicksort(pole, ++k, konec);
} else {
return;
}
}
Tak, a to je celé. Například takto může vypadat implementace tohoto algoritmu v jazyce Java.
Můžeme ovšem přidat ještě jednu metodu quicksort(int[] pole), která nám jen dodá pohodlí v používání tohoto algoritmu. V případě použití této metody využijeme polymorfismu a nemusíme zadávat zbytečně mnoho parametrů - bude stačit jen pole.
public static void quicksort(int pole[]) {
quicksort(pole, 0, pole.length - 1);
}
Ještě si na závěr dovolím drobné srovnání s algoritmem bubble sort v seřazení pole s těmito čísly {5, 4, 9, 1354, 3, 4564, 2, 1, 8, 6, 7, 10, 53, 14, 4, 59, 26, 58, 154788, 12, 45, 12, 457, 569885, 124, 484874, 4564, 2187, 564684, 1, 8, 48784, 145, 32, 5481}.
Rychlost seřazení algoritmem Quicksort - 44916 ns
Rychlost seřazení algoritmem Bubblesort - 72642 ns
