Zaradenie a popis

Bubble Sort je triediaci algoritmus, ktorý triedi prvky priamou výmenou.
Je implementačne jednoduchý, ale neefektívny, preto sa používa takmer výhradne iba na výuku.
Pohyb prvkov pri triedení pripomína stúpanie bubliniek, preto sa toto triedenie nazýva bublinkové triedenie.

^ TOP

Motivácia a špecifikácia

Máme v poli uloženú postupnosť prvkov. Cieľom je usporiadať (utriediť) túto postupnosť vzostupne (tj. od najmenšieho po najväčší prvok).
Vstup: pole A, ktoré je naplnené náhodnými hodnotami
Výstup: utriedené pole A

^ TOP

Myšlienka algoritmu

Postupne sa v cykle prechádza poľom, porovnávajú sa dva susedné prvky a ak nie sú v správnom poradí, vymenia sa.
Toto sa opakuje, až kým nie sú potrebné žiadne výmeny.

^ TOP

Vizualizácia

X-ová súradnica znázorňuje hodnotu prvku, Y-ová súradnica umiestnenie v poli.
Je vidieť, ako najväčšie prvky vždy "vybublú" na svoje miesto a tým posunú menšie prvky o jedno miesto nižšie.
Autor: Nuno Nogueira, zdroj: www.wikipedia.org

^ TOP

Zápis algoritmu

  procedure BubbleSort(var A: array of Integer);
  var
    I, J, T: Integer;
  begin
    for I := High(A) downto Low(A) do
     for J := Low(A) to High(A) - 1 do
       if A[J] > A[J + 1] then
       begin
         T := A[J];
         A[J] := A[J + 1];
         A[J + 1] := T;
       end;
  end;

^ TOP

Vlastnosti algoritmu

Časová zložitosť algoritmu je v priemernom prípade je O(n2).
V najhoršom prípade je časová zložitosť tiež O(n2).
Bubble Sort triedi porovnávaním, pracuje in situ (na mieste) a je stabilný - prvky s rovnakou hodnotou sú po utriedení v tom istom poradí ako na začiatku.
Algoritmus je veľmi neefektívny a mal by sa používať len na utriedenie málo prvkov (napr. 20).

^ TOP

Experimentovanie

Department of Computer Science, University of British Columbia, Canada
Java applety rôznych triediacich algoritmov.
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Computer Science Department, State University of New York, USA
Môžnosť experimentovať s algoritmom.
http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html

^ TOP