Lekce 2 - Bubblesort
V minulé lekci, Selection sort, jsme se seznámili s průběhem třídění prvků pomocí algoritmu Selection Sort.
Bubble sort je poměrně hloupý algoritmus, který se vyskytuje v podstatě jen v akademickém světě. Nemá žádné dobré vlastnosti a je zajímavý pouze svým průběhem, který může připomínat fyzikální nebo přírodní jevy. Algoritmus probíhá ve vlnách, přičemž při každé vlně propadne "nejtěžší" prvek na konec (nebo nejlehčí vybublá nahoru, záleží na implementaci). Vlna porovnává dvojice sousedních prvků a v případě, že je levý prvek větší než pravý, prvky prohodí. Algoritmus je stabilní.
Možná zlepšení
Algoritmus lze napsat úplně hloupě dvěma vnořenými for cykly s pevně daným počtem opakování (oba by proběhly tolikrát, jako je v poli prvků). Když se však trochu zamyslíme, zjistíme, že je zbytečné porovnávat nejtěžší prvky na "dně" pole, protože jsou již na správném místě. Vlny si tedy můžeme dovolit postupně zkracovat o 1 prvek a tu poslední tedy dokonce úplně vypustit.
Dalším zlepšením může být kontrola, zda pole není již náhodou setříděné, protože to se může snadno třeba v polovině běhu cyklů stát a je potom zbytečné v třídění pokračovat. Můžeme si jednoduše nastavit proměnnou prohozeno na false a při každém prohození nastavit tuto proměnnou na true. Pokud nakonci zjistíme, že jsme nic neprohodili (proměnná má hodnotu false), máme hotovo. Tyto 2 zlepšení obsahuje ukázkový průběh a níže i zdrojový kód.
Vrcholnou variantou "bublacího" algoritmu je tzv. Bubble sort s přetřásáním (Shaker sort neboli Cocktail sort), kde v každém běhu vnitřního cyklu proběhnou 2 vlny - jedna zleva doprava, tlačící těžší prvky dolů, druhá zprava, vynášející lehčí prvky nahoru. Odstraňuje to problém tzv. zajíců a želv, kde zajíci jsou těžké prvky, které se rychle propadají dolů. V původní implementaci jdou však lehké prvky nahoru jen velmi pomalu.
Vlastnosti algoritmu
Časová složitost | O (n2) |
---|---|
Stabilita | Ano |
Rychlost | Velmi špatná |
Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům.
Průběh
Protože Bubble sort je poněkud neoptimalizovaný algoritmus, bude průběh o něco delší, než bylo doposud zvykem.
Mějme pole následujících prvků:
3 | 2 | 5 | 1 | 9 | 4 |
První vlna projede celým polem a největší prvek "probublá" na konec.
3 | 2 | 5 | 1 | 9 | 4 |
Začneme tedy s vlnou a porovnáme první 2 prvky (3 a 2):
3 | 2 | 5 | 1 | 9 | 4 |
3 je jistě větší než 2, proto prvky prohodíme
2 | 3 | 5 | 1 | 9 | 4 |
Porovnáme další 2 prvky (3 a 5)
2 | 3 | 5 | 1 | 9 | 4 |
Ty jsou ve správném pořadí, takže je prohazovat nebudeme. Vlna pokračuje dále...
2 | 3 | 5 | 1 | 9 | 4 |
2 | 3 | 1 | 5 | 9 | 4 |
2 | 3 | 1 | 5 | 9 | 4 |
2 | 3 | 1 | 5 | 4 | 9 |
Po první vlně se maximum (9) opravdu probublalo na konec. Poslední prvek je tedy zatříděný a my si ho už nebudeme všímat. Další vlna bude o 1 prvek kratší, než předchozí, a vynese na konec maximum z nesetříděné části pole.
2 | 3 | 1 | 5 | 4 | 9 |
2 | 3 | 1 | 5 | 4 | 9 |
2 | 1 | 3 | 5 | 4 | 9 |
2 | 1 | 3 | 5 | 4 | 9 |
2 | 1 | 3 | 4 | 5 | 9 |
Po druhé vlně máme na konci již 2 setříděné prvky. Uděláme další vlnu.
2 | 1 | 3 | 4 | 5 | 9 |
1 | 2 | 3 | 4 | 5 | 9 |
1 | 2 | 3 | 4 | 5 | 9 |
1 | 2 | 3 | 4 | 5 | 9 |
Vidíme, že pole je nyní setříděné. Program by udělal ještě jednu vlnu a když by zjistil, že se nic neprohodilo, vrátil by výsledek.
Vizualizace
Video ukázka
Zdrojový kód
-
public static void bubbleSort(int[] list) { int j = list.length - 2, temp; // kontrola prohozeni boolean swapped = true; while (swapped) { swapped = false; for (int i = 0; i <= j; i++) { // prohozeni if (list[i] > list[i + 1]) { temp = list[i]; list[i] = list[i + 1]; list[i + 1] = temp; swapped = true; } } j--; } }
-
public static void bubbleSort(int[] list) { int j = list.Length - 2, temp; // kontrola prohozeni bool swapped = true; while (swapped) { swapped = false; for (int i = 0; i <= j; i++) { // prohozeni if (list[i] > list[i + 1]) { temp = list[i]; list[i] = list[i + 1]; list[i + 1] = temp; swapped = true; } } j--; } }
-
// setridi vlozene pole, predpoklada indexovani od 0 procedure bubble_sort(var list: array of integer); var i, j, temp: integer; swapped: boolean; begin j:=length(list) - 2; // kontrola prohozeni swapped:=true; while swapped do begin swapped:=false; for i:=0 to j do // prohozeni prvku if (list[i] > list[i + 1]) then begin temp:=list[i]; list[i]:=list[i + 1]; list[i + 1]:=temp; swapped:=true; end; dec(j); end; end;
-
# vraci setridene pole def bubble_sort(list) j = list.length - 2 # kontrola prohozeni swapped = true while (swapped) do swapped = false (j + 1).times do |i| # prohozeni if (list[i] > list[i + 1]) temp = list[i] list[i] = list[i + 1] list[i + 1] = temp swapped = true end end j -= 1 end end
-
Klikni pro editaci
{PHP} function bubbleSort(array &$list) { $j = count($list) - 2; // kontrola prohozeni $swapped = true; while ($swapped) { $swapped = false; for ($i = 0; $i <= $j; $i++) { // prohozeni if ($list[$i] > $list[$i + 1]) { $temp = $list[$i]; $list[$i] = $list[$i + 1]; $list[$i + 1] = $temp; $swapped = true; } } $j--; } } $list = [28, 3, 2, 18, 2, 17, 14, 8]; bubbleSort($list); print_r($list); {/PHP}
Zkontroluj, zda výstupy programu odpovídají předloze. S jinými texty testy neprojdou.
-
Public Sub Bubblesort(cisla() As Integer) Dim j As Integer = cisla.Length - 2 Dim pomocna As Integer Dim prohozeno As Boolean = True ' kontrola prohození While prohozeno prohozeno = False For i As Integer = 0 To j If cisla(i) > cisla(i + 1) Then ' prohození pomocna = cisla(i) cisla(i) = cisla(i + 1) cisla(i + 1) = pomocna prohozeno = True End If Next j -= 1 End While End Sub
V další lekci, Insertion sort, si ukážeme algoritmus Insertion sort i se zdrojovými kódy.