Zhrnutie na Rýchle triedenie (quicksort)

Rýchle triedenie (Quicksort): Podrobný rozbor pre študentov

Zhrnutie Test znalostí Kartičky Podcast Myšlienková mapa

Úvod do Rýchleho Triedenia (Quicksort)

Rýchle triedenie, známejšie pod anglickým názvom Quicksort, je jedným z najvýznamnejších a najpoužívanejších triediacich algoritmov v informatike. Vytvoril ho britský informatik T. A. R. Hoare v roku 1959. Je to porovnávací triediaci algoritmus, čo znamená, že usporadúva prvky na základe ich vzájomného porovnávania. Medzi jeho kľúčové výhody patrí vysoká efektívnosť v priemernom prípade a relatívne jednoduchá implementácia, pričom nevyžaduje dodatočnú pamäť pre celé pole, čo z neho robí triediaci algoritmus „na mieste“ (in-place).

Triediaci algoritmus „na mieste“ (in-place): Algoritmus, ktorý transformuje vstup s použitím len malého množstva dodatočného úložného priestoru. Tento priestor je typicky považovaný za konštantný ($O(1)$) alebo logaritmický ($O(\log n)$) vzhľadom na veľkosť vstupu.

Princíp algoritmu „Rozdeľ a panuj“

Quicksort je ukážkovým príkladom algoritmu, ktorý implementuje stratégiu „rozdeľ a panuj“ (divide and conquer). Jeho základná logika je rozdelená do troch krokov:

Rozdeľ (Divide): Z poľa sa vyberie jeden prvok, ktorý sa nazýva pivot. Pole sa potom rozdelí na dve (alebo potenciálne tri) podpolia. Všetky prvky, ktoré sú menšie ako pivot, sú presunuté do ľavého podpoľa, zatiaľ čo prvky väčšie ako pivot sú umiestnené v pravom podpoli. Prvky rovné pivotu môžu byť umiestnené v ktoromkoľvek z týchto podpolí alebo v samostatnom treťom podpoli. Po dokončení tohto kroku sa pivot nachádza na svojej finálnej pozícii v utriedenom poli.
Panuj (Conquer): Na takto vytvorené dve (alebo tri) podpolia sa rekurzívne aplikuje rýchle triedenie.
Spoj (Combine): Tento krok je triviálny. Vzhľadom na to, že podpolia sú už utriedené a pivot je na správnej pozícii, po rekurzívnom utriedení podpolí je celé pole automaticky utriedené.

💡 Vedeli ste?Did you know, že T. A. R. Hoare údajne vyvinul Quicksort, keď sa snažil triediť slová na preklad z ruštiny do angličtiny, a pôvodne ho naprogramoval v assembleri pre počítač Elliott 803?

Voľba Pivota

Výber pivota má kľúčový vplyv na výkon algoritmu Quicksort. Ideálna voľba pivota by viedla k rozdeleniu poľa presne na dve rovnako veľké podpolia. Nájdenie takéhoto pivota v praxi je však výpočtovo náročné. Preto sa používajú rôzne stratégie:

Prvý alebo posledný prvok: Toto je najjednoduchšia implementácia. Ak je však pole už usporiadané alebo takmer usporiadané, môže to viesť k najhoršiemu scenáru časovej zložitosti ($O(n^2)$).
Stredný prvok: Výber prvku nachádzajúceho sa v strede poľa. Hoci je to lepšie ako prvý/posledný prvok pre niektoré typy dát, stále existuje riziko najhoršieho prípadu.
Náhodný prvok: Pivot sa vyberie náhodne z poľa. Táto metóda znižuje pravdepodobnosť najhoršieho prípadu pre akékoľvek konkrétne vstupné dáta, ale negarantuje optimálny výkon v každom spustení.
Medián z troch: Táto stratégia zahŕňa výber mediánu spomedzi prvého, stredného a posledného prvku poľa. Je robustnejšia a často vedie k lepšiemu výkonu, pretože znižuje šancu na výber extrémneho prvku ako pivota.

Lomutoho schéma rozdelenia (Partitioning)

Existuje viacero schém na rozdelenie poľa okolo pivota. Jednou z najznámejších a často používaných je Lomutoho schéma rozdelenia. Predpokladajme, že pivot je vybraný ako posledný prvok v aktuálnom podpoli. Postup je nasledujúci:

Vyberie sa pivot (napríklad posledný prvok A[koniec]).
Inicializuje sa index $i$ (pre menšie prvky) na začiatok - 1.
Prechádza sa poľom od začiatok po koniec - 1 s indexom $j$.
Ak je $A[j]$ menšie alebo rovné pivotu: a. Zvýši sa $i$ o $1$. b. Vymenia sa prvky $A[i]$ a $A[j]$.
Po dokončení cyklu sa vymenia prvky $A[i+1]$ a $A[koniec]$ (pivot).
Funkcia vráti index $i+1$, čo je finálna pozícia pivota.

Po tomto kroku sú všetky prvky vľavo od $i+1$ menšie alebo rovné pivotu a všetky prvky vpravo od $i+1$ sú väčšie ako pivot.

Príklad Lomutoho rozdelenia

Ukážme si Lomutoho rozdelen

Zaregistruj sa pre celé zhrnutie

KartičkyTest znalostíZhrnutiePodcastMyšlienková mapa

Začni zadarmo

Už máš účet? Prihlásiť sa

Rýchle Triedenie Quicksort

Klíčová slova: Algoritmus rýchleho triedenia (Quicksort), Algoritmus Quicksort

Klíčové pojmy: Quicksort je porovnávací triediaci algoritmus založený na princípe „rozdeľ a panuj“., Algoritmus bol vyvinutý T. A. R. Hoareom v roku 1959., Je to triediaci algoritmus „na mieste“ (in-place), čo znamená, že vyžaduje minimálnu dodatočnú pamäť., Krok „Rozdeľ“ zahŕňa výber pivota a rozdelenie poľa na menšie a väčšie prvky ako pivot., Krok „Panuj“ rekurzívne aplikuje triedenie na podpolia., Krok „Spoj“ je triviálny, pretože podpolia sú už utriedené a pivot je na správnej pozícii., Voľba pivota zásadne ovplyvňuje výkon Quicksortu, ideálny pivot delí pole na dve rovnaké časti., Stratégie výberu pivota zahŕňajú prvý/posledný prvok, stredný prvok, náhodný prvok a medián z troch., Lomutoho schéma rozdelenia je populárny spôsob, ako rozdeliť pole okolo pivota., V Lomutoho schéme sú prvky menšie alebo rovné pivotu presunuté naľavo a väčšie napravo od pivota., Priemerná časová zložitosť Quicksortu je $O(n \log n)$, zatiaľ čo najhoršia je $O(n^2)$.

## Úvod do Rýchleho Triedenia (Quicksort) Rýchle triedenie, známejšie pod anglickým názvom Quicksort, je jedným z najvýznamnejších a najpoužívanejších triediacich algoritmov v informatike. Vytvoril ho britský informatik T. A. R. Hoare v roku 1959. Je to **porovnávací triediaci algoritmus**, čo znamená, že usporadúva prvky na základe ich vzájomného porovnávania. Medzi jeho kľúčové výhody patrí vysoká efektívnosť v priemernom prípade a relatívne jednoduchá implementácia, pričom nevyžaduje dodatočnú pamäť pre celé pole, čo z neho robí triediaci algoritmus „na mieste“ (in-place). > **Triediaci algoritmus „na mieste“ (in-place)**: Algoritmus, ktorý transformuje vstup s použitím len malého množstva dodatočného úložného priestoru. Tento priestor je typicky považovaný za konštantný ($O(1)$) alebo logaritmický ($O(\log n)$) vzhľadom na veľkosť vstupu. ### Princíp algoritmu „Rozdeľ a panuj“ Quicksort je ukážkovým príkladom algoritmu, ktorý implementuje stratégiu „rozdeľ a panuj“ (divide and conquer). Jeho základná logika je rozdelená do troch krokov: 1. **Rozdeľ (Divide):** Z poľa sa vyberie jeden prvok, ktorý sa nazýva **pivot**. Pole sa potom rozdelí na dve (alebo potenciálne tri) podpolia. Všetky prvky, ktoré sú menšie ako pivot, sú presunuté do ľavého podpoľa, zatiaľ čo prvky väčšie ako pivot sú umiestnené v pravom podpoli. Prvky rovné pivotu môžu byť umiestnené v ktoromkoľvek z týchto podpolí alebo v samostatnom treťom podpoli. Po dokončení tohto kroku sa pivot nachádza na svojej finálnej pozícii v utriedenom poli. 2. **Panuj (Conquer):** Na takto vytvorené dve (alebo tri) podpolia sa rekurzívne aplikuje rýchle triedenie. 3. **Spoj (Combine):** Tento krok je triviálny. Vzhľadom na to, že podpolia sú už utriedené a pivot je na správnej pozícii, po rekurzívnom utriedení podpolí je celé pole automaticky utriedené. Did you know, že T. A. R. Hoare údajne vyvinul Quicksort, keď sa snažil triediť slová na preklad z ruštiny do angličtiny, a pôvodne ho naprogramoval v assembleri pre počítač Elliott 803? ### Voľba Pivota Výber pivota má kľúčový vplyv na výkon algoritmu Quicksort. Ideálna voľba pivota by viedla k rozdeleniu poľa presne na dve rovnako veľké podpolia. Nájdenie takéhoto pivota v praxi je však výpočtovo náročné. Preto sa používajú rôzne stratégie: * **Prvý alebo posledný prvok:** Toto je najjednoduchšia implementácia. Ak je však pole už usporiadané alebo takmer usporiadané, môže to viesť k najhoršiemu scenáru časovej zložitosti ($O(n^2)$). * **Stredný prvok:** Výber prvku nachádzajúceho sa v strede poľa. Hoci je to lepšie ako prvý/posledný prvok pre niektoré typy dát, stále existuje riziko najhoršieho prípadu. * **Náhodný prvok:** Pivot sa vyberie náhodne z poľa. Táto metóda znižuje pravdepodobnosť najhoršieho prípadu pre akékoľvek konkrétne vstupné dáta, ale negarantuje optimálny výkon v každom spustení. * **Medián z troch:** Táto stratégia zahŕňa výber mediánu spomedzi prvého, stredného a posledného prvku poľa. Je robustnejšia a často vedie k lepšiemu výkonu, pretože znižuje šancu na výber extrémneho prvku ako pivota. ### Lomutoho schéma rozdelenia (Partitioning) Existuje viacero schém na rozdelenie poľa okolo pivota. Jednou z najznámejších a často používaných je **Lomutoho schéma rozdelenia**. Predpokladajme, že pivot je vybraný ako posledný prvok v aktuálnom podpoli. Postup je nasledujúci: 1. Vyberie sa pivot (napríklad posledný prvok `A[koniec]`). 2. Inicializuje sa index $i$ (pre menšie prvky) na `začiatok - 1`. 3. Prechádza sa poľom od `začiatok` po `koniec - 1` s indexom $j$. 4. Ak je $A[j]$ menšie alebo rovné pivotu: a. Zvýši sa $i$ o $1$. b. Vymenia sa prvky $A[i]$ a $A[j]$. 5. Po dokončení cyklu sa vymenia prvky $A[i+1]$ a $A[koniec]$ (pivot). 6. Funkcia vráti index $i+1$, čo je finálna pozícia pivota. Po tomto kroku sú všetky prvky vľavo od $i+1$ menšie alebo rovné pivotu a všetky prvky vpravo od $i+1$ sú väčšie ako pivot. #### Príklad Lomutoho rozdelenia Ukážme si Lomutoho rozdelen