Bubble sort je již dlouho dobu známý algoritmus. Používá se ovšem spíše pro výuku, protože je nesmírně pomalý. Existuje mnoho dalších efetivnějších algoritmů pro řazení, jako jsou například - merge sort, quicksort a nebo třeba řazení haldou (heapsort). Většina s těchto dalších algoritmů mají menší asymptotickou složitost a to O(n log n), zatímco bubble sort dosahuje až O(n²).
Na druhou stranu má bubble sort nesmírnou jednoduchost zápisu a snadnou implementaci.
Algoritmus funguje velice jednoduchým způsobem. Prostě jen porovnává dvě vedlejší čísla a když je číslo na levé straně větší, tak tyto dvě čísla zamění. Následující animace se snaží znázornit, jak bubble sort řadí "zaměňuje" čísla.
Příklad, který zde uvedu se bude skládat z dvou cyklů for. Samozřejmě existují různá řešení tohoto cyklu. Například výpočetnímu výkonu by trochu ulehčilo použití do{}while().
Tady už máme statickou metodu, která vrací pole celých čísel. Její vstupní parametr int[] cisla je také pole celých čísel.
public static int[] bubblesort(int[] cisla) {
for(int i = 1;i < cisla.length;i++) {
for(int j = cisla.length-1; j >= i;j--) {
if(cisla[j] < cisla[j-1]) {
int tmp = cisla[j-1];
cisla[j-1] = cisla[j];
cisla[j] = tmp;
}
}
}
return cisla;
}
Nyní již tuto metodu můžeme používat a řadit s ní pole celých čísel.
int[] rozhazenaCisla = {4, 8, 9, 1, 3, 2, 7, 5, 6};
int[] serazenaCisla = bubblesort(rozhazenaCisla);
for(int i = 0; i < rozhazenaCisla.length;i++) {
System.out.print(rozhazenaCisla[i] + " ");
}
Zde jsme vlastně jen vytvořili pole celých čísel int[] rozhazenaCisla, které jsme naplnili rozházenými čísly 1-9. Poté jsme vytvořili int[] serazenaCisla a na jeho naplnění jsme zavolali metodu bubblesort() se vstupním parametrem rozhazenaCisla - metoda bubblesort() nám čísla seřadila a vrátila je poli serazenaCisla. Závěrečným cyklem jen vypíšeme seřazené hodnoty. V tomto případe - 1 2 3 4 5 6 7 8 9
2008-11-05 16:56:31
Moc dobře si vybavuji hodinu ve škole, když jsme toto brali. Jeden učitel(říkali jsme mu česnek), který učil také VT přišel do třídy a zeptal se našeho učitele, kterého jsme měli(říkali jsme mu Vocy), tak ten česnek se zetal "Co to je?" a Vocas na to "To je Bablsort". Česnek pak odešel plný radosti, že se něco nového dozvěděl :D:D