Bubble sort (bublinkové řazení) je jednoduchý
stabilní řadící algoritmem se složitostí . Vylepšením bubble sortu je shakersort (oboustranný
bubble sort).
Princip
Pokud si představíme řazená čísla jako bublinky, tak ty s menší hodnotou jsou lehčí než ty s vyšší hodnotou a stoupají proto ve vodě rychleji.
Obdobně postupuje také bubble sort. Porovnává dva sousední prvky, a pokud je nižší číslo nalevo od vyššího, tak je prohodí (nižší číslo je lehčí a rychleji stoupá ke konci pole) a se stejnou logikou pokračuje na dalším indexu. Pokud jsou čísla ve správném pořadí, tak je neprohodí – pouze postoupí dále (algoritmus tím našel lehčí bublinku). Na konci iterace se tímto způsobem na konec pole vždy dostane ta nejlehčí bublinka (nejnižší číslo). Nyní algoritmus můžeme pustit znovu na redukovaný problém (na poslední pozici pole je již to správné číslo).
Po n-1 průchodech (poslední bublinka je seřazena triviálně) je pole seřazeno.
Vizualizace
Příklad
(3 2 8 7 6) // 3 a 2 jsou v korektním pořadí, posuňme se o index
(3 2 8 7 6) // 8 > 2, prohoďme je
(3 8 2 7 6) // 7 > 2, prohoďme je (zde je vidět probublávání nejlehčí dvojky vzhůru)
(3 8 7 2 6) // 6 > 2, prohoďme je
(3 8 7 6 2) // nový průchod polem: na posledním místě je nejlehčí prvek, tudíž se nám řazená úloha o jedna zkrátila, 8 > 3, prohoďme je
(8 3 7 6 2) // 7 > 3, prohoďme je
(8 7 3 6 2) // 6 > 3, prohoďme je
(8 7 6 3 2) // seřazeno
Kód
function bubbleSort(array a)
for i in 1 -> a.length - 1 do
for j in 1 -> a.length - i - 1 do
if a[j] < a[j+1]
prohoď(a[j], a[j+1]);
/**
* Bublinkove razeni (od nejvyssiho)
* @param array pole k serazeni
*/
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if(array[j] < array[j+1]){
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
/**
* Bublinkove razeni (od nejmensiho)
* @param array pole k serazeni
* @param size velikost pole
*/
void bubbleSort(int * array, int size){
for(int i = 0; i < size - 1; i++){
for(int j = 0; j < size - i - 1; j++){
if(array[j+1] < array[j]){
int tmp = array[j + 1];
array[j + 1] = array[j];
array[j] = tmp;
}
}
}
}
/**
* Bublinove razeni (od nejmensiho po nejvetsiho)
* @param arr pole k serazeni
* @author Thomas (www.adamjak.net)
*/
static void BubbleSort(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = 0; j < arr.Length - i - 1; j++)
{
if (arr[j + 1] < arr[j])
{
int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}
}
/**
* Bubble sort (descending order)
* @param array array to be sorted
* @auhor Pavel Micka
*/
function bubbleSort(array){
for (var i = 0; i < array.length - 1; i++) {
for (var j = 0; j < array.length - i - 1; j++) {
if(array[j] < array[j+1]){
var tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
procedure BubbleSort(var X : ArrayType; N : integer);
var
I,
J : integer;
begin
for I := 2 to N do
begin
for J := N downto I do
if (X[J] > X[J - 1]) then
Swap(X[J - 1], X[J]);
end
end;
procedure Swap(var X, Y : integer);
var
Temp : integer;
begin
Temp := X;
X := Y;
Y := Temp
end;
/**
* Bublinkove razeni (od nejmensiho po nejvetsiho)
* @param $arr pole, ktere bude usporadano
* @author Thomas (www.adamjak.net)
*/
function bubble_sort(&$arr) {
$count = count($arr);
for($i = 0; $i < $count - 1; $i++) {
for($j = 0; $j < $count - $i - 1; $j++) {
if($arr[$j + 1] < $arr[$j]) {
$tmp = $arr[$j + 1];
$arr[$j + 1] = $arr[$j];
$arr[$j] = $tmp;
}
}
}
}
Rozbor
K seřazení pole bude zapotřebí celkem vnějších cyklů, protože při každém
průchodu seřadíme jeden prvek na konec pole (tímto postupně zmenšujeme úlohu,
proto se každým průchodem zmenšuje i počet procházených prvků ve vnitřním cyklu)
a poslední prvek již není třeba řadit (jeden prvek je triviálně seřazen).
Poslední částí algoritmu je vnitřní podmíka, ve které orientace znaménka rozhoduje, zda-li budeme řadit vzestupně nebo sestupně.
Složitost
Vnitřní cyklus se provede
Což je celkem
sčítanců a podle vzorce na aritmetickou posloupnost je počet operací
Což je asymptoticky (lineární funkce a konstanta rostou asymptoticky pomaleji,
můžeme je zanedbat). Protože jde jak o nejhorší, tak o nejlepší případ, je
výsledná asymptotická složitost
.