Bubblesort

Algoritmy Třídění Bubblesort

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

Autorem widgetu s vizualizací je Jenkings

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (8 hlasů) :
4.8754.8754.8754.8754.875


 


Miniatura
Předchozí článek
Selection sort
Miniatura
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Insertion sort

 

 

Komentáře

Avatar
Petr
Neregistrovaný
Avatar
Petr:

Díky 8-)

 
Odpovědět 27.1.2012 0:18
Avatar
olaznik
Člen
Avatar
olaznik:

Prosímtě v tom druhém řádku, jak je ( int j = list.length - 2 ) proč tam odečítáš 2 ?? díky za odpověd. Měj se.

Editováno 9.12.2014 12:49
 
Odpovědět 9.12.2014 12:47
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na olaznik
Jan Vargovský:

Klasicky jede cyklus od i do < length, ale on použil <= proto tam musí být length - 1 a protože porovnává aktuální prvek a ten za ním, tak tam musí být length - 2;

 
Odpovědět 9.12.2014 14:30
Avatar
Jozef
Člen
Avatar
Jozef:

C

void bubbleSort(int list[],int size) {
  // kontrola prohozeni
  int swapped = 1,temp;
  while (swapped) {
    swapped = 0;
    for (int i = 0; i < size; i++) {
      // prohozeni
      if (list[i] > list[i + 1]) {
        temp = list[i];
        list[i] = list[i + 1];
        list[i + 1] = temp;
        swapped = 1;
      }
    }
    size--;
  }
}
Odpovědět  -1 21.3.2015 0:00
I'm not afraid to die on a treadmill
Avatar
Martin
Člen
Avatar
Martin:

Vyzeral by ShakerSort (v jave) nejak takto alebo je tam ešte možné zlepšenie ?

public static void ShakerSort(int[]list){
        int j = list.length-2;
        int temp;
        boolean swapped = true;
        while(swapped)
        {
            swapped = false;
            for(int i = 0;i<=j;i++)
            {
                if(list[i]>list[i+1])
                {
                    temp     = list[i];
                    list[i]  = list[i+1];
                    list[i+1]= temp;
                    swapped = true;
                }

             }
            for(int i = j; i>0;i--)
            {
                if(list[i]<list[i-1])
                {
                    temp     = list[i];
                    list[i]  = list[i-1];
                    list[i-1]= temp;
                    swapped = true;
                }
            }
            j--;
        }
    }
 
Odpovědět 24. listopadu 17:39
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.