Bubble sort

Bubble sort (bublinkové řazení) je jednoduchý stabilní řadící algoritmem se složitostí O(n^2) . 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) //zadání pole, řaďmě od největšího k nejmenšímu
(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 n-1 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

(n-1) + (n-2) + (n-3) + ... + (1) krát.

Což je celkem n-1 sčítanců a podle vzorce na aritmetickou posloupnost je počet operací

(pocetScitancu) * ((prvni + posledni)/2) = (n-1)*(n-1+1)/2 = (n² - n)/2

Což je asymptoticky $n^{2}$ (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 $\\Theta(n^{2})$ .

Princip

Vizualizace

Příklad

Kód

Rozbor

Složitost

Doporučujeme