# Rychlé řazení (Quicksort) Rychlé řazení, známé jako Quicksort, je jeden z nejefektivnějších a nejčastěji používaných řadicích algoritmů. Byl vyvinut Tonym Hoarem v roce 1959. Patří do kategorie algoritmů „rozděl a panuj“ (divide and conquer) a je proslulý svou rychlostí v průměrném případě a relativně jednoduchou implementací. Quicksort pracuje **in-place**, což znamená, že nepotřebuje mnoho dodatečné paměti. Díky své efektivitě je široce využíván v různých aplikacích, od databázových systémů po operační systémy. ## Princip algoritmu „rozděl a panuj“ Základní myšlenka rychlého řazení spočívá v rekurzivním rozdělení velkého problému na menší, snadněji řešitelné podproblémy. Algoritmus pracuje následovně: 1. **Vyber pivot:** Z pole prvků je vybrán jeden prvek, nazývaný **pivot**. Tento prvek slouží jako referenční bod pro dělení pole. 2. **Rozděl pole (partition):** Ostatní prvky pole jsou přeskupeny tak, že všechny prvky menší než pivot jsou umístěny před ním a všechny prvky větší než pivot jsou umístěny za ním. Prvky rovné pivotu mohou být umístěny na libovolnou stranu. Po tomto kroku je pivot na své konečné seřazené pozici. 3. **Rekurzivně seřaď podpole:** Algoritmus je rekurzivně aplikován na podpole prvků menších než pivot a na podpole prvků větších než pivot. Základní případ rekurze nastává, když podpole obsahuje nula nebo jeden prvek, které jsou již považovány za seřazené a nevyžadují další zpracování. > ### Rozděl a panuj (Divide and Conquer) > Jedná se o algoritmickou techniku, která řeší problém tak, že ho rekurzivně rozděluje na dva nebo více podproblémů stejného nebo podobného typu, dokud nejsou dostatečně jednoduché na to, aby mohly být přímo vyřešeny. Řešení podproblémů jsou pak kombinována k získání řešení původního problému. ### Příklad průběhu rychlého řazení Představte si, že máme pole čísel: $[5, 2, 8, 1, 9, 4, 7]$. 1. **Krok 1: Výběr pivota.** Zvolíme si například poslední prvek jako pivot. V tomto případě je to $7$. Pole: $[5, 2, 8, 1, 9, 4, \underline{7}]$ (pivot je $7$) 2. **Krok 2: Rozdělení pole.** Přeskupíme prvky tak, aby všechny menší než $7$ byly nalevo a větší napravo. Po rozdělení (partitioning) může pole vypadat například takto: $[5, 2, 1, 4, \underline{7}, 9, 8]$. Pivot $7$ je nyní na své konečné pozici. 3. **Krok 3: Rekurzivní volání.** Nyní máme dvě podpole k seřazení: * Podpole menších prvků: $[5, 2, 1, 4]$ * Podpole větších prvků: $[9, 8]$ Algoritmus Quicksort je rekurzivně aplikován na $[5, 2, 1, 4]$ (zvolíme pivot, rozdělíme, atd.) a na $[9, 8]$ (zvolíme pivot, rozdělíme, atd.). Tento proces se opakuje, dokud každé podpole nemá nula nebo jeden prvek. Did you know, že v průměrném případě je časová složitost Quicksortu $O(n \log n)$, kde $n$ je počet prvků k seřazení? To z něj činí velmi rychlý algoritmus pro velké datové sady. ## Volba pivota Výběr pivota má zásadní vliv na výkon rychlého řazení. Špatná volba může vést k nejhoršímu případu složitosti, zatímco dobrá volba zajistí efektivní běh. ### Strategie pro volbu pivota: * **První nebo poslední prvek:** * **Popis:** Nejjednodušší implementace, pivot je vždy první nebo poslední prvek aktuálního podpole. * **Problém:** Pokud je vstupní pole již seřazené nebo téměř seřazené, tato volba vede k nejhoršímu případu, protože pivot bude vždy nejmenší nebo největší prvek. To způsobuje nevyvážené dělení, kdy jedno podpole je téměř prázdné a druhé téměř stejně velké jako původní. * **Složitost v nejhorším případě:** $O(n^2)$. * **Náhodný prvek:** * **Popis:** Pivot je vybrán náhodně z prvků v aktuálním podpoli. * **Výhody:** Pomáhá zabránit nejhoršímu případu pro specifické vstupní datové sady, které by mohly „podvést“ statické volby pivota. Zvyšuje pravděpodobnost, že se algoritmus bude chovat jako v průměrném případě. * **Nevýhody:** Nezaručuje vždy průměrný výkon; náhodný výběr má vlastní režii. * **Medián ze tří:** * **Popis:** Vybe