Podcast o Rýchle triedenie (quicksort)

Kapitoly

Jedna vec, ktorá rozhoduje

Princíp Rozdeľ a panuj

Kľúčová voľba pivota

Lomutoho schéma v praxi

Dokončenie rozdelenia

Rýchly... alebo pomalý?

Přepis

Natália: Predstav si, že na písomke z informatiky dostaneš za úlohu utriediť obrovské pole čísel čo najrýchlejšie. Je tu jedna vec, na ktorej sa potkne osemdesiat percent študentov. My ti dnes ukážeme, ako sa tejto chybe navždy vyhnúť.

Lukáš: A nielen to. Ukážeme ti, ako vďaka tomu získať plný počet bodov. Je to jednoduchšie, než si myslíš.

Natália: Počúvate Studyfi Podcast. Tak poďme na to, Lukáš. Dnes je témou rýchle triedenie, známejšie asi ako Quicksort.

Lukáš: Presne tak. Quicksort je jeden z najpoužívanejších triediacich algoritmov, a to z dobrého dôvodu – je extrémne rýchly. Jeho autor, Tony Hoare, prišiel s geniálnym princípom „rozdeľ a panuj“.

Natália: Rozdeľ a panuj? To znie trochu ako vojenská stratégia. Ako to funguje pri triedení čísel?

Lukáš: Je to presne tak! Princíp je jednoduchý a má tri kroky. Najprv pole rozdelíš, potom nad časťami panuješ a nakoniec to celé spojíš.

Natália: Dobre, tak poďme na prvý krok. Rozdelenie.

Lukáš: Vyberieme si jeden prvok, ktorému hovoríme pivot. Potom celé pole preskupíme tak, aby všetky čísla menšie ako pivot boli naľavo a všetky väčšie napravo. Tým sa pivot dostane na svoju finálnu, správnu pozíciu.

Natália: Aha! Takže ten pivot je kľúčový. A toto je tá vec, ktorú študenti často pokazia, však?

Lukáš: Presne si to trafila! Výber pivota je absolútne zásadný. Ak si vyberieš zle, napríklad vždy prvý alebo posledný prvok v takmer utriedenom poli, celý algoritmus sa extrémne spomalí.

Natália: Tak ako si vybrať správne? Aké sú najlepšie stratégie?

Lukáš: Najrobustnejšia metóda, ktorú odporúčam aj na písomky, je „medián z troch“. Zoberieš prvý, stredný a posledný prvok poľa a ako pivota použiješ ten prostredný z nich. Tým sa vyhneš extrémnym hodnotám.

Natália: Super, takže pivota máme. Ale ako to preskupenie reálne prebieha? Znie to dosť chaoticky.

Lukáš: Vôbec nie! Existuje na to elegantný postup, napríklad Lomutoho schéma rozdelenia. Ukážeme si ju na príklade poľa: 7, 2, 1, 6, 8, 5, 3, 4.

Natália: Dobre, som zvedavá. Čo bude náš pivot?

Lukáš: Pre jednoduchosť si teraz zvoľme posledný prvok, teda číslo 4. Na začiatku si určíme pomocný index, povedzme i, na pozíciu mínus jedna. Potom prechádzame poľom zľava doprava.

Natália: A čo robíme pri prechádzaní?

Lukáš: Vždy, keď narazíme na číslo menšie alebo rovné pivotu, teda štvorke, posunieme index i o jedna dopredu a vymeníme prvky na pozícii i a na našej aktuálnej pozícii. Takže keď narazíme na dvojku, i sa posunie na nulu a vymeníme ju so sedmičkou.

Natália: Rozumiem! Takže postupne presúvame všetky menšie čísla na začiatok poľa.

Lukáš: Presne tak. A keď prejdeme celé pole, už len vymeníme nášho pivota, tú štvorku, s prvkom na pozícii i+1. Tým sa pivot dostane presne medzi menšie a väčšie prvky. A hotovo, pole je rozdelené.

Lukáš: ...a sme presne v polovici. Pokračujeme ďalej v cykle, index j sa posunie na štvorku.

Natália: Super, zatiaľ to dáva zmysel. Čo sa stane ďalej?

Lukáš: Na pozícii štyri je hodnota osem. Je osem väčšia ako náš pivot, štvorka?

Natália: Áno, je. Takže sa nič nemení?

Lukáš: Presne. Nič sa nedeje, j sa jednoducho posunie ďalej. To isté platí pre pozíciu päť, kde je hodnota päť. Päťka je väčšia ako štvorka.

Natália: Okej, takže len preskakujeme prvky, ktoré sú už na správnej strane od pivota.

Lukáš: Presne tak! Ale teraz prichádza zmena. Keď j skočí na pozíciu šesť, nájdeme tam hodnotu tri.

Natália: A trojka je menšia ako štvorka. Takže teraz akcia!

Lukáš: Presne, akcia! Zvýšime i na dvojku a vymeníme prvky na pozíciách i a j. Teda A a A. Chápeš?

Natália: Áno, pole teraz vyzerá... . Cyklus skončil. Čo teraz?

Lukáš: Posledný, kľúčový krok. Vymeníme prvok na pozícii A s naším pivotom, ktorý bol celý čas na konci.

Natália: Takže prvok na indexe tri, čo je šestka, vymeníme za štvorku na konci.

Lukáš: Presne! Výsledok je pole . A náš pivot, štvorka, je na svojom finálnom mieste! Vľavo sú menšie čísla, vpravo väčšie.

Natália: Perfektné! A teraz sa to isté rekurzívne opakuje pre tú ľavú a pravú časť.

Lukáš: Presne tak. A tým sa dostávame k otázke rýchlosti.

Natália: Volá sa Quicksort, takže musí byť rýchly, nie?

Lukáš: Väčšinou áno. V priemernom prípade má časovú zložitosť O(n log n), čo je extrémne efektívne. Patrí medzi najrýchlejšie triediace algoritmy.

Natália: Ale počujem tam jedno