Podcast o Bublinkové triedenie (bubble sort)

Kapitoly

Úvod do triedenia

Čo je bublinkové triedenie?

Ako funguje bublanie?

Krok za krokom na príklade

Rýchlosť a efektivita (Zložitosť)

Dá sa to zrýchliť? (Optimalizácia)

Najčastejšie chyby

Zhrnutie a záver

Přepis

Filip: Predstav si, že dohráš kolo v obľúbenej hre a hneď ti naskočí rebríček najlepších hráčov. Tvoje meno poskočí o pár miest vyššie... Zamyslel si sa niekedy, ako presne ten počítač vie v zlomku sekundy zoradiť všetkých hráčov od najlepšieho po najhoršieho?

Ema: To je skvelá otázka, Filip. Väčšina z nás to berie ako samozrejmosť. Ale za týmto jednoduchým zoradením sa skrýva svet algoritmov. A presne jeden z nich, ten úplne najzákladnejší, je dôvod, prečo sme dnes tu.

Filip: Takže dnes odhalíme tajomstvo herných rebríčkov? Som za!

Ema: Presne tak. Vitajte pri Studyfi Podcast.

Filip: Dobre, Ema, tak aký je ten tajomný algoritmus? Znie to ako niečo super zložité.

Ema: Práve naopak. Volá sa bublinkové triedenie, alebo po anglicky Bubble Sort. A je známy tým, že je jedným z najjednoduchších triediacich algoritmov vôbec.

Filip: Bublinkové triedenie? Ten názov znie celkom milo. Prečo práve bublinkové?

Ema: Pretože prvky sa v zozname správajú ako bublinky vo vode. Tie ľahšie, teda menšie čísla, postupne „vybublú“ na začiatok, zatiaľ čo ťažšie, väčšie čísla, klesajú na koniec. Je to veľmi vizuálne.

Filip: Aha, takže je to dobrý algoritmus na začiatok, ak sa chcem učiť o triedení?

Ema: Presne tak. Je skvelý na pochopenie základných princípov. Ale, a to je dôležité, v praxi pre veľké množstvo dát je extrémne pomalý a neefektívny. Takže v tom hernom rebríčku ho dnes už asi nenájdeš.

Filip: Dobre, takže je to taký náš tréningový sparing partner vo svete algoritmov. Ukáže nám základy, ale na majstrovstvá sveta ho nepošleme.

Ema: Perfektné prirovnanie! Je kľúčový pre pochopenie, ale pre reálne aplikácie máme oveľa silnejších hráčov.

Filip: Tak poďme na to. Ako teda to „bublanie“ presne funguje?

Ema: Základná myšlienka je veľmi jednoduchá. Algoritmus opakovane prechádza zoznamom a porovnáva vždy len dva susedné prvky.

Filip: Okej, len susedov?

Ema: Áno. A ak sú v nesprávnom poradí – napríklad pri triedení od najmenšieho po najväčší je prvé číslo väčšie ako druhé – tak ich jednoducho vymení.

Filip: A to je všetko? Len porovnáš dvoch susedov a ak treba, vymeníš ich?

Ema: V jednom kroku áno. Ale tento proces opakuješ pre celý zoznam. Prejdeš od začiatku do konca, porovnávaš dvojicu za dvojicou. Po jednom takomto kompletnom prechode sa stane jedna zaujímavá vec.

Filip: A to aká?

Ema: Najväčší prvok z celého zoznamu zaručene „prebublal“ až na úplný koniec, na svoju správnu pozíciu. Ako tá najťažšia guľôčka, čo klesla na dno.

Filip: Chápem! Takže po prvom kole máme istotu, že posledný prvok je na správnom mieste. A čo ďalej?

Ema: No, a potom to celé zopakujeme znova. Ale s malým vylepšením – už nemusíme ísť až na úplný koniec, lebo ten posledný prvok je už vybavený. Takže v druhom kole dostaneme na správne miesto druhý najväčší prvok a tak ďalej.

Filip: Dobre, teória znie fajn, ale ja som typ, čo to potrebuje vidieť. Ukážme si to na príklade. Povedzme, že máme zoznam čísel: 5, 1, 4, 2, 8.

Ema: Super voľba. Takže, počiatočný zoznam je . Ideme na prvý prechod. Začíname zľava. Porovnáme prvú dvojicu: 5 a 1. Je 5 väčšie ako 1?

Filip: Áno, je.

Ema: Tak ich vymeníme. Náš zoznam teraz vyzerá takto: . Jednoduché, však?

Filip: Zatiaľ áno. Čo ďalej?

Ema: Posunieme sa o jednu pozíciu doprava. Teraz porovnávame 5 a 4. Opäť, 5 je väčšie ako 4, takže...?

Filip: Vymeníme ich! Zoznam je . Už tomu prichádzam na chuť.

Ema: Výborne. Ďalšia dvojica je 5 a 2. Zase výmena. Máme . A posledná dvojica v tomto prechode je 5 a 8.

Filip: Tu je 5 menšie ako 8, takže sú v správnom poradí. Nič nemeníme.

Ema: Presne tak! A pozri sa, čo sa stalo. Po prvom prechode je náš zoznam . Najväčšie číslo, osmička, je na úplnom konci. Je „usadená“.

Filip: A je tam správne! Takže na ňu už môžeme zabudnúť. Čo druhý prechod?

Ema: V druhom prechode robíme to isté, ale už ideme len po predposledný prvok. Porovnáme 1 a 4 – bez zmeny. Potom 4 a 2 – tu meníme. Zoznam je . Ďalej porovnáme 4 a 5 – bez zmeny.

Filip: Počkaj, počkaj... veď ten zoznam je už teraz dokonale zoradený!

Ema: Správny postreh! Ale ten základný, „hlúpy“ algoritmus to ešte nevie. Bude pokračovať ďalej, aj keď už nie sú potrebné žiadne výmeny. A presne k tomu sa dostaneme pri optimalizácii.

Filip: Takže, prečo je vlastne taký pomalý, ak je taký jednoduchý? Spomínala si nejakú zložitosť.

Ema: Áno, časová zložitosť. V informatike ju označujeme ako notáciu „Veľké O“. Je to spôsob, ako meriame, o koľko viac práce musí algoritmus urobiť, keď mu dáme viac dát.

Filip: Znie to ako z maturity z matiky. Skús to prosím jednoducho.

Ema: Jasné. Predstav si to takto. Pre bublinkové triedenie platí, že ak zdvojnásobíš počet prvkov v zozname, čas potrebný na triedenie sa zhruba zoštvornásobí. To je zlé.

Filip: Zoštvornásobí? To je dosť veľa. Prečo?

Ema: Pretože pre zoznam s 'n' prvkami potrebuje urobiť zhruba n na druhú, čiže n² operácií. V našom príklade s 5 prvkami to nebolo také zlé. Ale predstav si zoznam s 1000 prvkami.

Filip: 1000 na druhú... to je milión. Milión porovnaní! Uf, tak to by som rukou robiť nechcel.

Ema: Presne. Preto hovoríme, že má časovú zložitosť O(n²). Je to kvadratická zložitosť a pre veľké dáta je to pohroma. Na druhej strane má jednu veľkú výhodu: priestorovú zložitosť.

Filip: A to je čo?

Ema: Nepotrebuje takmer žiadnu pamäť navyše, bez ohľadu na to, aký veľký je zoznam. Vystačí si s dočasnou premennou na výmenu prvkov. To je super, a preto hovoríme, že jeho priestorová zložitosť je konštantná, O(1).

Filip: V našom príklade sme si všimli, že zoznam bol zoradený skôr, než algoritmus skončil. Spomínala si, že sa to dá vylepšiť. Ako?

Ema: Veľmi jednoducho a šikovne. Pridáme si takú malú vlajočku, alebo premennú, ktorú na začiatku každého prechodu nastavíme na „nebolo výmeny“.

Filip: Dobre, máme vlajku. Čo s ňou?

Ema: Ak počas prechodu dôjde k akejkoľvek výmene prvkov, tú vlajku zdvihneme a povieme si „áno, bola výmena“. A na konci prechodu sa na tú vlajku pozrieme.

Filip: A ak zostala dole? Teda ak sa nič nevymenilo...

Ema: Presne! Ak sa za celý prechod neurobila ani jedna jediná výmena, čo to znamená?

Filip: Že všetko je už na svojom mieste! Zoznam je zoradený!

Ema: Bingo! A v tom momente môžeme algoritmus okamžite zastaviť a ďalej sa netrápiť. Nemusíme robiť zbytočné prechody až do konca.

Filip: Takže v našom príklade by sa to zastavilo už po treťom prechode, lebo v ňom by sa už nič nemenilo.

Ema: Presne tak. Táto optimalizácia dramaticky zlepší výkon v takzvanom „najlepšom prípade“. Ak dostaneš zoznam, ktorý je už zoradený, vďaka tejto vlajke prejde zoznamom len raz a hneď skončí. Jeho zložitosť vtedy klesne na O(n), čo je oveľa lepšie.

Filip: Okej, vyzerá to celkom priamočiaro. Sú nejaké typické chyby, ktoré študenti robia, keď sa to učia programovať?

Ema: Určite. Najčastejšou je asi pomýliť si hranice cyklov. To je to, dokedy má algoritmus porovnávať. Ak to nastavíš zle, buď ti nedotriedi celý zoznam, alebo sa ti program zrúti, lebo sa snaží siahnuť na prvok, ktorý neexistuje.

Filip: Klasická chyba „index out of bounds“. Poznám, stalo sa.

Ema: Presne tá. Ďalšou chybou je mylná predstava o efektivite. Tým, že je algoritmus taký jednoduchý na pochopenie a napísanie, ľudia si niekedy myslia, že je aj dobrý. Ale je dôležité pamätať na tú strašidelnú zložitosť O(n²).

Filip: Čiže, je fajn na pohovor na juniorskú pozíciu, aby si ukázal, že rozumieš základom, ale reálny produkt na ňom nepostavíš.

Ema: Presne si to vystihol. A ešte jedna vec: nezabúdať na tú optimalizáciu s vlajočkou. Nezachráni to síce ten najhorší prípad, ale ukazuje to dôležitý princíp: vždy premýšľaj, či sa tvoj kód nedá zastaviť skôr, ak už dosiahol svoj cieľ.

Filip: Super, Ema, toto bolo veľmi zrozumiteľné. Skúsme si to teda na záver zhrnúť. Čo je to najdôležitejšie, čo by sme si mali o bublinkovom triedení zapamätať?

Ema: Po prvé, je to jednoduchý, základný triediaci algoritmus. Jeho princípom je porovnávanie a výmena susedných prvkov. Menšie prvky „bublú“ nahor.

Filip: Po druhé, po každom prechode sa najväčší prvok dostane na svoje finálne miesto.

Ema: Presne. Po tretie, jeho veľkou nevýhodou je časová zložitosť O(n²), čo ho robí nepoužiteľným pre veľké dáta. Naopak, výhodou je priestorová zložitosť O(1), lebo nepotrebuje extra pamäť.

Filip: A po štvrté, dá sa jednoducho optimalizovať pomocou vlajky, ktorá sleduje, či došlo k výmene. Ak nie, algoritmus môže skončiť skôr.

Ema: Perfektné zhrnutie. Ak pochopíte toto, máte zvládnuté bublinkové triedenie a skvelý základ pre porovnávanie s efektívnejšími algoritmami.

Filip: Výborne. Ďakujeme, že ste nás počúvali. Dúfam, že vám to pomôže nielen na písomke z informatiky, ale aj pri pohľade na ďalší herný rebríček.

Ema: Majte sa pekne a dopočutia nabudúce!

Filip: Dopočutia.