# Bublinkové řazení (Bubble Sort) Bublinkové řazení, známé též pod anglickým názvem Bubble Sort, je jedním z nejjednodušších řadicích algoritmů. Jeho princip spočívá v opakovaném procházení seznamu prvků, porovnávání sousedních dvojic a jejich prohození, pokud nejsou ve správném pořadí. Tento proces se opakuje, dokud není celý seznam seřazen. Název „bublinkové“ je odvozen od skutečnosti, že větší prvky se postupně „probublávají“ na konec seznamu, podobně jako bublinky stoupají k hladině. ## Princip fungování Základní myšlenka bublinkového řazení je velmi intuitivní. Představte si neseřazený seznam čísel. Algoritmus začne na začátku seznamu a porovná první dva prvky. Pokud je první prvek větší než druhý, prohodí je. Poté se posune o jednu pozici dál a porovná druhý a třetí prvek, a opět je prohodí, pokud jsou ve špatném pořadí. Tento proces pokračuje až do konce seznamu. Po dokončení jednoho takového průchodu je zaručeno, že největší prvek z aktuálně procházené (nesetříděné) části seznamu se ocitne na své správné pozici na konci této části. Celý algoritmus se skládá z několika takových průchodů. V každém průchodu se postupně „probublá“ další největší prvek na své místo. Po prvním průchodu je největší prvek v celém seznamu na svém místě na konci. Po druhém průchodu je druhý největší prvek na svém místě před tím největším, a tak dále. Algoritmus končí, když už žádný průchod neprovede žádnou výměnu, což znamená, že seznam je již seřazen. > **Řadicí algoritmus:** Algoritmus, který uspořádá prvky seznamu (pole, souboru) do určitého pořadí, například vzestupného nebo sestupného. ## Průchody a jejich mechanismus Pro lepší pochopení si představme seznam s $n$ prvky. Bublinkové řazení provádí $n-1$ průchodů v nejhorším případě. V každém $i$-tém průchodu (kde $i$ jde od $0$ do $n-2$) se porovnávají a případně prohazují prvky od začátku seznamu až po $n-1-i$-tý prvek. Důvodem je, že po $i$ průchodech je posledních $i$ prvků seznamu již seřazeno a na svých správných pozicích, a proto je není třeba znovu kontrolovat. **Příklad průchodu:** Mějme seznam $[5, 1, 4, 2, 8]$. Délka seznamu $n = 5$. **První průchod ($i = 0$):** 1. Porovnej $5$ a $1$. $5 > 1$, takže prohodíme: $[1, 5, 4, 2, 8]$ 2. Porovnej $5$ a $4$. $5 > 4$, takže prohodíme: $[1, 4, 5, 2, 8]$ 3. Porovnej $5$ a $2$. $5 > 2$, takže prohodíme: $[1, 4, 2, 5, 8]$ 4. Porovnej $5$ a $8$. $5 < 8$, neprohazujeme: $[1, 4, 2, 5, 8]$ Po prvním průchodu je největší prvek $8$ na svém místě na konci seznamu. Seznam je $[1, 4, 2, 5, 8]$. Poslední prvek ($8$) je nyní seřazen. **Druhý průchod ($i = 1$):** Nyní budeme porovnávat pouze prvky do předposlední pozice (index $n-1-i = 5-1-1 = 3$). 1. Porovnej $1$ a $4$. $1 < 4$, neprohazujeme: $[1, 4, 2, 5, 8]$ 2. Porovnej $4$ a $2$. $4 > 2$, takže prohodíme: $[1, 2, 4, 5, 8]$ 3. Porovnej $4$ a $5$. $4 < 5$, neprohazujeme: $[1, 2, 4, 5, 8]$ Po druhém průchodu je druhý největší prvek ($5$) na svém místě. Seznam je $[1, 2, 4, 5, 8]$. Poslední dva prvky ($5, 8$) jsou nyní seřazeny. **Třetí průchod ($i = 2$):** Porovnáváme pouze prvky do pozice $n-1-i = 5-1-2 = 2$. 1. Porovnej $1$ a $2$. $1 < 2$, neprohazujeme: $[1, 2, 4, 5, 8]$ 2. Porovnej $2$ a $4$. $2 < 4$, neprohazujeme: $[1, 2, 4, 5, 8]$ Po třetím průchodu je třetí největší prvek ($4$) na svém místě. Seznam je $[1, 2, 4, 5, 8]$. Poslední tři prvky ($4, 5, 8$) jsou nyní seřazeny. **Čtvrtý průchod ($i = 3$):** Porovnáváme pouze prvky do pozice $n-1-i = 5-1-3 = 1$. 1. Porovnej $1$ a $2$. $1 < 2$, neprohazujeme: $[1, 2, 4, 5, 8]$ Po čtvrtém průchodu je seznam $[1, 2, 4, 5, 8]$ kompletně seřazen. Zajímavost: Bublinkové řazení je často využíváno jako první příklad řadicího algoritmu při výuce informatiky kvůli své jednoduchosti a intuitivnímu fungování, ačkoli v praxi se pro větší datové sady používají mnohem efektivnější algoritmy. ## Optimalizace bublinkového řazení Základní implementace bublinkového řazení provede vždy $n-1$ průchodů, i když je seznam seřazen dříve. To lze optimalizovat přidá