Podcast na Srovnání řadicích algoritmů a časová složitost

Kapitoly

Úvod do řazení

Metriky pro srovnání

Seznamte se: Bubble Sort

Přepis

Filip: Když jsi dnes ráno otevřel sociální sítě, všiml sis, jak jsou příspěvky seřazené? Nebo když si pustíš playlist na Spotify? Není to náhoda. Za tím vším je motor, který neustále něco organizuje a přeskládává... a právě o tom si dnes budeme povídat. Posloucháte Studyfi Podcast.

Tereza: Přesně tak! A těmto motorům se říká řadicí algoritmy. Jsou to vlastně takoví super-rychlí uklízeči dat. Jejich úkolem je vzít hromadu prvků, třeba čísel nebo jmen, a seřadit je podle nějakého pravidla – třeba od nejmenšího po největší.

Filip: Dobře, takže máme spoustu dat a potřebujeme v nich udělat pořádek. Ale proč je tolik různých algoritmů? Není jeden univerzálně nejlepší?

Tereza: Skvělá otázka! Není, protože každý se hodí na něco jiného. Představ si to jako nástroje. Na malý šroubek taky nevezmeš obří kladivo. Algoritmy porovnáváme podle několika kritérií. Nejdůležitější je asi časová složitost.

Filip: To zní... složitě.

Tereza: Vůbec ne! Jen to měří, jak moc se algoritmus „zapotí“, když mu dáš víc práce. Třeba jestli seřazení tisíce položek trvá dvakrát déle než u pěti set, nebo jestli to trvá tisíckrát déle. To nám říká takzvaná notace Velké O.

Filip: Aha! Takže O(n²) je horší než O(n log n), protože to roste mnohem rychleji.

Tereza: Přesně tak! Dále koukáme na paměťovou složitost – kolik paměti si algoritmus musí „půjčit“ navíc. A taky na stabilitu. Stabilní algoritmus zachová původní pořadí prvků se stejnou hodnotou, což se hodí, když třídíš podle více kritérií.

Filip: Pojďme na konkrétní příklad. Který algoritmus je takový ten „základní kámen“, na kterém se to všichni učí?

Tereza: To bude určitě Bubble Sort, neboli bublinkové řazení. Jeho princip je krásně jednoduchý. Opakovaně procházíš seznam, porovnáváš dva sousední prvky, a pokud jsou ve špatném pořadí, prohodíš je.

Filip: Takže to je jako když bublinky v limonádě stoupají nahoru? Ty lehčí, tedy menší hodnoty, postupně „probublají“ na začátek seznamu?

Tereza: To je perfektní přirovnání! Přesně tak to funguje. Je to intuitivní, ale má to háček. Pro velké seznamy je to extrémně pomalé. Jeho časová složitost je právě to obávané O(n²).

Filip: Takže na seřazení mého playlistu s tisíci písničkami by to asi nebylo to pravé, co?

Tereza: To by sis na hudbu asi chvíli počkal. Ale pro pochopení základních principů řazení je to naprosto ideální start.