Bublinkové triedenie

Z Wikipédie

Bublinkové triedenie (ang. bubble sort) je implementačne jednoduchý výmenný triedaci 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.

[úprava] Algoritmus

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

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

[úprava] Zložitosť

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

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.