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 = (n2 - 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}).

Hodnocení (19): 4,47

Přečtěte si také

Diskuse





Kukuksumusu8.11.2014
Implementace v C++ neni spravne (proc se ve vnitrnim for cyklu odcita ta jednicka?).
magulos6.10.2014
ja chci taky kalvados :(
Roman Wyka6.10.2014
Ale pánové,
namísto programování bubblesortu, tady máte
vášnivou diskuzi o vanách a kalvadosu!
Vaginální lovec6.10.2014

package javaapplication22;
import java.util.Scanner;

public class JavaApplication22 {


public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Součet, dokud uživatel nepřesáhne součet 1000");


int soucet = 0;

int prekroceni = 0;
int pocet=0;
while(soucet <= 1000){

System.out.print("Zadej číslo: ");

int x = sc.nextInt();
soucet = soucet + x;
pocet++;



}
prekroceni = soucet - 1000;
System.out.println("Výsledné číslo je: " +soucet);
System.out.println("Příklad byl překročen o : "+prekroceni);
System.out.println("Počet čísel"+pocet);



}
}
magul6.10.2014
hej kam to vkládate, pošlete celý zdroják. Diky
ady kralis6.10.2014
package pole;
import java.util.Scanner;
public class Pole {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int []a = new int[20];
int min = 100;
int max = 0;
System.out.println("Autor: Petr Macko");
System.out.println();

for (int i = 0 ; i < a.length ; i++)
{
a[i] = (int)Math.round(Math.random()*100 +1);
System.out.println("Číslo " + i + ". pole je " + a[i]);
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}

}
System.out.println("Maximální číslo je: " + max);
System.out.println("Minimální číslo je: " + min);
rici266.10.2014
ahoj ja jsem rici a delam s bubble sortem. Je to pěkné.
Jurgin696.10.2014
Najs nebo najs nápovědka u babl zortu.
Honza4.9.2014
výborné, velice mi to pomohlo
Coti je do toho25.8.2014
Jak to zkopíruju do pascalu?
Karel16.5.2014
ahoj GH IVT sem 1 :)
petra30.4.2014
super článek, moc děkuji autorovi :)
roman 25.4.2014
ja to nechapu ja jenom nevim jak to mam sestavit potrebuju nekoho kdo mi s tim malinko pomuze prosim piste kdyz tak na email wolfman399@email.cz predem dekuju
Majkl19.6.2013
Je to vážně hezké akorát jsem to stejně trochu nepochopil v JavaScriptu, jinak to je ale úžasné
MaŠle16.3.2013
Výborně vysvětleno + animace. díky moc
musicmaker14.3.2013
Nádherně vysvětleno, animace:=gr8; :D :D
Elopes12.2.2013
Krásná vizualizace :)
Pavel Mička15.10.2012
> Hans

To už je vylepšení bubble sort, zde jsem prezentoval jeho základní implementaci. Ono stejně nějak zásadně vylepšovat bubble sort nemá příliš velký smysl, protože je stejně dosti pomalý...
Hans15.10.2012
Takhle by mě to nikdy nenapadlo implementovat. Podle mého by vnější cyklus měl checkovat podmínku, jestli se při posledním průchodu vnitřního cyklu stala nějaká změna. Tím při setříděném listu máme náročnost pouze n a n^2 je v nejhorším případě.
Viz např: http://rosettacode.org/wiki/Bubble_Sort#C
Pavel Mička28.4.2011
Díky za upozornění, to neodečítání v C++ byla chyba. Už je to opravené.
Lamorak28.4.2011
Tento kod funguje pouze pokud size je o jedna mensi nez realny pocet prvku v poli.. v ukazce pro javu se jednicka odecita, proc ne tady?