Bublinkové triedenie

Bublinkové triedenie (ang. bubble sort) je implementačne jednoduchý výmenný triediaci algoritmus. Pracuje na mieste a nepatrí medzi prirodzené triediace algoritmy. Je pre praktické účely neefektívny.

Pracuje opakovaným prechodom cez zoznam, ktorý má byť utriedený porovnávajúc vždy dva prvky. Ak prvky nie sú v správnom poradí zamení ich. Porovnávanie prvkov v zozname trvá, pokiaľ sú potrebné výmeny, teda pokiaľ nie je zoznam usporiadaný. Algoritmus dostal názov vďaka tomu, že menšie prvky sa „prebublinkujú“ na začiatok zoznamu.

Algoritmus

Poznámka: toto je len jedna z variácií algoritmu.

Pre i od 1 po (počet prvkov)
  Pre j od 1 po (počet prvkov - i)
    Ak zoznam[j] > zoznam[j+1]
      Vymeň zoznam[j] ↔ zoznam[j+1]

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;

Zložitosť

Asymptotická priemerná aj najhoršia zložitosť bublinkového triedenia je $O(n^2)$.

Tento algoritmus triedenia je jedným z najhorších, oproti iným algoritmom s rovnakou rádovou zložitosťou vyžaduje veľa zápisov do pamäte a neefektívnu prácu s cache procesora. Takmer neexistuje prípad, kedy by mal nejakú výhodu oproti iným postupom.