Bublinkové řazení (bubble sort)

Podcast

Řadicí algoritmy: Od bublinek k rychlosti0:00 / 9:43

0:001:00 zbývá

1x

Bublinkové řazení, známé též pod anglickým názvem Bubble Sort, je jedním z nejzákladnějších a nejjednodušších řadicích algoritmů. Je to skvělý úvod do světa algoritmů pro řazení a pochopení jeho principů je klíčové pro studenty informatiky. Algoritmus opakovaně prochází seznam prvků, porovnává sousední dvojice a prohazuje je, pokud nejsou ve správném pořadí, dokud není celý seznam seřazen.

Co je Bublinkové Řazení (Bubble Sort) a jak funguje?

Princip bublinkového řazení spočívá v intuitivním postupu. Algoritmus začíná na začátku seznamu a porovnává první dva prvky. Pokud je první prvek větší než druhý, prohodí je.

Poté se posune o jednu pozici dál a porovná další sousední dvojici, opět je prohodí, pokud jsou ve špatném pořadí. Tento proces pokračuje až do konce seznamu.

Název „bublinkové“ je odvozen od toho, že větší prvky se postupně „probublávají“ na konec seznamu, podobně jako bublinky stoupají k hladině. 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. Algoritmus končí, když už žádný průchod neprovede žádnou výměnu, což znamená, že seznam je již seřazen.

Detailní průchody bublinkového řazení

Pro lepší pochopení mechanismu bublinkového řazení si představme seznam s n prvky. Algoritmus 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 pro zkracování rozsahu porovnání je, že po i průchodech je posledních i prvků seznamu již seřazeno a na svých správných pozicích. Proto je není třeba znovu kontrolovat. Podívejme se na konkrétní příklad:

Příklad průchodu s optimalizací: 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.

Optimalizace a složitost 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áním příznaku, který sleduje, zda v daném průchodu došlo k nějaké výměně.

Pokud se v celém průchodu neprovede žádná výměna, znamená to, že seznam je již seřazen a algoritmus může předčasně skončit. Tato optimalizace výrazně zlepší výkon v nejlepším případě.

Časová složitost Bubble Sort

Složitost algoritmu se obvykle vyjadřuje pomocí notace velkého O. To popisuje, jak se doba běhu algoritmu mění s velikostí vstupu n.

• Nejhorší případ (Worst Case): O(n²).
• Nastává, když je seznam seřazen v opačném pořadí. Algoritmus musí provést maximální počet porovnání a výměn. Pro n prvků je potřeba n-1 průchodů. Celkový počet porovnání je přibližně n²/2.
• Průměrný případ (Average Case): O(n²).
• Pro náhodně seřazený seznam je časová složitost stále kvadratická, protože i zde je potřeba mnoho průchodů a výměn.
• Nejlepší případ (Best Case): O(n).
• Nastává, když je seznam již seřazen a je použita optimalizace pro předčasné ukončení. Algoritmus provede pouze jeden průchod bez výměny a poté se ukončí. Počet porovnání je n-1, což je lineární složitost.

Prostorová složitost Bubble Sort

Bublinkové řazení je tzv. řazení na místě (in-place sorting). To znamená, že nepotřebuje žádnou dodatečnou paměť, která by rostla s velikostí vstupu. Výjimkou je jen několik proměnných pro dočasné uložení prvků během výměny.

• Prostorová složitost: O(1).

Pseudokód a implementace v Pythonu

Zde naleznete pseudokód a praktickou implementaci bublinkového řazení v Pythonu, která zahrnuje optimalizaci pro předčasné ukončení.

Pseudokód bublinkového řazení

procedura bublinkove_razeni(seznam):
 n = délka(seznam)
 opakuj:
 vymeneno = NEPRAVDA
 pro i od 0 do n - 2:
 pokud seznam[i] > seznam[i + 1]:
 prohod(seznam[i], seznam[i + 1])
 vymeneno = PRAVDA
 n = n - 1 // Optimalizace: poslední prvek je již na svém místě
 dokud vymeneno je PRAVDA

Kód v Pythonu s optimalizací

def bublinkove_razeni(seznam):
 n = len(seznam)

 # Procházíme celý seznam
 for i in range(n - 1):
 # Příznak pro sledování, zda došlo k výměně v aktuálním průchodu
 vymeneno = False
 # Posledních i prvků je již na svém místě, takže je nemusíme kontrolovat
 for j in range(n - 1 - i):
 # Porovnáme sousední prvky
 if seznam[j] > seznam[j + 1]:
 # Prohodíme je, pokud jsou ve špatném pořadí
 seznam[j], seznam[j + 1] = seznam[j + 1], seznam[j]
 vymeneno = True
 # Pokud v tomto průchodu nedošlo k žádné výměně, seznam je seřazen
 if not vymeneno:
 break
 return seznam

# Příklad použití:
muj_seznam = [64, 34, 25, 12, 22, 11, 90]
serazeny_seznam = bublinkove_razeni(muj_seznam)
print("Seřazený seznam je:", serazeny_seznam)

muj_seznam_2 = [5, 1, 4, 2, 8]
serazeny_seznam_2 = bublinkove_razeni(muj_seznam_2)
print("Seřazený seznam 2 je:", serazeny_seznam_2)

muj_seznam_3 = [1, 2, 3, 4, 5] # Již seřazený seznam
serazeny_seznam_3 = bublinkove_razeni(muj_seznam_3)
print("Seřazený seznam 3 je:", serazeny_seznam_3)

Časté chyby a mylné představy o bublinkovém řazení

Při studiu a implementaci bublinkového řazení se studenti často setkávají s několika běžnými chybami a nepochopeními. Je důležité si je uvědomit, abyste se jich vyvarovali.

1. Nepochopení principu „bublání“: Někteří studenti si myslí, že bublinkové řazení přesune prvek na jeho konečnou pozici v jednom kroku. Ve skutečnosti se prvek „probublává“ postupně, krok za krokem, v rámci jednoho průchodu.
2. Nesprávné rozsahy cyklů: Častou chybou je nastavení nesprávných hranic pro vnitřní nebo vnější cyklus. To může vést k chybám indexování nebo k neúplnému seřazení. Je důležité si uvědomit, že vnitřní cyklus se zkracuje s každým vnějším průchodem, protože poslední prvky jsou již seřazeny.
3. Zapomenutí optimalizace: Mnoho implementací bublinkového řazení opomíjí optimalizaci pro předčasné ukončení. Ačkoli to nemění asymptotickou časovou složitost v nejhorším případě, výrazně zlepšuje výkon pro částečně nebo zcela seřazené vstupní datové sady.
4. Předpoklad efektivity: Bublinkové řazení je často mylně považováno za efektivní algoritmus pro všechny případy. Jeho kvadratická složitost O(n²) ho však činí velmi neefektivním pro velké datové sady. V těchto případech jsou preferovány algoritmy s lepší složitostí, jako je rychlé řazení (Quick Sort) nebo řazení slučováním (Merge Sort).

Bublinkové řazení v simulaci: interaktivní pozorování

Interaktivní simulace bublinkového řazení umožňuje studentům vizualizovat a pochopit mechanismus algoritmu krok za krokem. Při práci se simulací si můžete všimnout následujících jevů:

1. Krokování porovnání a výměn: Simulace názorně ukazuje, jak se prvky porovnávají a kdy dochází k jejich výměně. Uvidíte, jak se větší prvky postupně posouvají doprava (nebo menší doleva) v každém průchodu. To pomáhá pochopit, proč se algoritmus nazývá „bublinkové“.
2. Postupné usazování prvků: Po každém dokončeném průchodu si všimněte, že jeden prvek (největší z dosud nesetříděné části) se usadí na své konečné pozici na konci seznamu. Simulace často zvýrazňuje tyto již seřazené prvky, aby bylo jasné, která část seznamu je již hotová.
3. Vliv vstupních dat na bublinkové řazení:

• Náhodná data: Pro náhodně uspořádaný seznam uvidíte mnoho porovnání a výměn, což demonstruje složitost O(n²).
• Seřazená data: Pokud zadáte již seřazený seznam a simulace implementuje optimalizaci předčasného ukončení, uvidíte, že algoritmus provede pouze jeden průchod bez výměn a rychle se ukončí. To ilustruje nejlepší případ O(n).
• Opačně seřazená data: Pro seznam seřazený v opačném pořadí uvidíte maximální počet porovnání a výměn, což je typický příklad nejhoršího případu O(n²).

4. Počet operací: Simulace často zobrazuje počítadla porovnání a výměn. Sledujte, jak se tato čísla mění v závislosti na velikosti a uspořádání vstupního seznamu. To vám pomůže kvantifikovat efektivitu (nebo neefektivitu) bublinkového řazení a pochopit, proč je jeho časová složitost kvadratická.

Interakce se simulací vám umožní experimentovat s různými vstupními daty a vizuálně sledovat, jak algoritmus pracuje. To je klíčové pro hlubší pochopení jeho principů a omezení, což ocení každý student.

Často kladené otázky o bublinkovém řazení

Proč se bublinkové řazení nazývá „bublinkové“?

Název „bublinkové řazení“ vychází z pozorování, že větší prvky se v každém průchodu postupně „probublávají“ směrem ke konci seznamu. Podobně jako bublinky stoupají k hladině, tak i největší prvky stoupají na své správné pozice.

Je bublinkové řazení efektivní pro velké datové sady?

Ne, bublinkové řazení není efektivní pro velké datové sady. Jeho průměrná a nejhorší časová složitost je O(n²), což znamená, že doba běhu se výrazně zvyšuje s rostoucím počtem prvků. Pro velké sady dat jsou vhodnější algoritmy s lepší složitostí, například Quick Sort nebo Merge Sort.

Co je to optimalizace pro předčasné ukončení bublinkového řazení?

Optimalizace pro předčasné ukončení znamená, že pokud v jednom celém průchodu bublinkového řazení nedojde k žádné výměně prvků, algoritmus usoudí, že seznam je již seřazen, a ukončí se. To výrazně zlepšuje výkon v nejlepším případě, kdy je seznam již seřazen nebo téměř seřazen.

Jaká je prostorová složitost bublinkového řazení?

Prostorová složitost bublinkového řazení je O(1). To znamená, že algoritmus potřebuje pouze konstantní množství dodatečné paměti, nezávisle na velikosti vstupu. Říkáme mu proto „řazení na místě“ (in-place sorting).

Jaké jsou nejčastější chyby při implementaci bublinkového řazení?

Mezi nejčastější chyby patří nepochopení principu postupného „bublání“, nesprávné nastavení rozsahů cyklů (vedoucí k chybám indexování nebo neúplnému seřazení) a zapomenutí na implementaci optimalizace pro předčasné ukončení. Další chybou je mylný předpoklad o jeho efektivitě pro všechny případy.