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.