# Úvod do bublinkového triedenia Bublinkové triedenie (angl. Bubble Sort) je jedným z najzákladnejších triediacich algoritmov, ktorý sa často používa ako úvod do štúdia algoritmov v informatike. Jeho hlavnou výhodou je **ľahká pochopiteľnosť a implementácia**. Napriek svojej jednoduchosti je však pre väčšie dátové súbory neefektívny, čo ho robí nevhodným pre praktické aplikácie, kde je dôležitý výkon. Jeho štúdium je však kľúčové pre pochopenie základných princípov triedenia a analýzy zložitosti algoritmov. ## Princíp bublinkového triedenia Základná myšlienka bublinkového triedenia spočíva v opakovanom prechádzaní zoznamu prvkov a porovnávaní každej dvojice susedných prvkov. Ak sú prvky v nesprávnom poradí (napríklad prvý je väčší ako druhý pri vzostupnom triedení), vymenia sa. Tento proces sa opakuje, kým nie je celý zoznam usporiadaný. Po každom prechode zoznamom sa najväčší (alebo najmenší, v závislosti od smeru triedenia) nesprávne umiestnený prvok „prebublá“ na svoju správnu pozíciu na konci (alebo začiatku) už triedenej časti zoznamu. Odtiaľ pochádza aj názov „bublinkové triedenie“ – prvky sa správajú ako bublinky, ktoré stúpajú na hladinu. > **Triedenie:** Proces usporiadania dát do určitého poradia (vzostupného alebo zostupného). ## Prechody algoritmom Algoritmus bublinkového triedenia funguje na princípe viacerých prechodov (iterácií) cez zoznam. Predstavme si zoznam s $n$ prvkami. V každom prechode sa vykoná séria porovnaní a prípadných výmen: 1. **Prvý prechod:** Algoritmus začína porovnávaním prvého a druhého prvku. Ak sú v nesprávnom poradí, vymenia sa. Potom sa porovná druhý a tretí prvok atď., až po $(n-1)$-tý a $n$-tý prvok. Po dokončení prvého prechodu je zaručené, že najväčší prvok v zozname sa nachádza na poslednej pozícii. Táto pozícia je už „triedená“ a v ďalších prechodoch sa s ňou už nepracuje. 2. **Druhý prechod:** Algoritmus opäť prechádza zoznamom, ale tentoraz len po $(n-1)$-tú pozíciu, pretože $n$-tá pozícia už obsahuje správny prvok. Po dokončení tohto prechodu bude druhý najväčší prvok na $(n-1)$-tej pozícii. 3. **Ďalšie prechody:** Tento proces sa opakuje. V každom prechode sa počet porovnávaných prvkov znižuje o jeden, pretože jeden prvok je už na svojej správnej pozícii. Celkovo je potrebných $(n-1)$ prechodov na úplné usporiadanie zoznamu. ## Príklad krok za krokom Ukážme si bublinkové triedenie na príklade zoznamu čísel: $[5, 1, 4, 2, 8]$. Cieľom je usporiadať zoznam vzostupne. Počiatočný zoznam: $[5, 1, 4, 2, 8]$ Počet prvkov ($n$) = $5$ **Prvý prechod ($i = 0$):** Porovnávame prvky od začiatku po predposledný (index $3$). * Porovnať $5$ a $1$: $5 > 1$, vymeniť. Zoznam: $[1, 5, 4, 2, 8]$ * Porovnať $5$ a $4$: $5 > 4$, vymeniť. Zoznam: $[1, 4, 5, 2, 8]$ * Porovnať $5$ a $2$: $5 > 2$, vymeniť. Zoznam: $[1, 4, 2, 5, 8]$ * Porovnať $5$ a $8$: $5 < 8$, nevymeniť. Zoznam: $[1, 4, 2, 5, 8]$ Po prvom prechode je najväčší prvok ($8$) na správnej pozícii na konci zoznamu. Posledný prvok ($8$) je teraz triedený. Zoznam po prvom prechode: $[1, 4, 2, 5, 8]$ **Druhý prechod ($i = 1$):** Porovnávame prvky od začiatku po index $2$ (predposledný netriedený prvok). * Porovnať $1$ a $4$: $1 < 4$, nevymeniť. Zoznam: $[1, 4, 2, 5, 8]$ * Porovnať $4$ a $2$: $4 > 2$, vymeniť. Zoznam: $[1, 2, 4, 5, 8]$ * Porovnať $4$ a $5$: $4 < 5$, nevymeniť. Zoznam: $[1, 2, 4, 5, 8]$ Po druhom prechode je druhý najväčší prvok ($5$) na správnej pozícii. Posledné dva prvky ($5, 8$) sú triedené. Zoznam po druhom prechode: $[1, 2, 4, 5, 8]$ **Tretí prechod ($i = 2$):** Porovnávame prvky od začiatku po index $1$ (predposledný netriedený prvok). * Porovnať $1$ a $2$: $1 < 2$, nevymeniť. Zoznam: $[1, 2, 4, 5, 8]$ * Porovnať $2$ a $4$: $2 < 4$, nevymeniť. Zoznam: $[1, 2, 4, 5, 8]$ Po treťom prechode je tretí najväčší prvok ($4$) na správnej pozícii. Posledné tri prvky ($4, 5, 8$) sú triedené. Zoznam po treťom prechode: $[1, 2, 4, 5, 8]$ **Štvrtý prechod ($i = 3$):** Porovnávame prvky od začiatku