Bublinkové triedenie
Znova a znova prechádza zoznam a vymieňa susedov, ktorí sú v nesprávnom poradí. Po každom prechode je najväčšia zostávajúca hodnota na konci.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- áno
- áno
Najlepší prípad: ako rastie čas s veľkosťou zoznamu n, keď je vstup pre tento algoritmus najľahší.
Priemerný: obvyklý rast času s n. Pri n² trvá dvakrát viac hodnôt asi štyrikrát dlhšie; n log n rastie oveľa pomalšie.
Najhorší: rast času na najťažšom vstupe. Dôležitý, keď sa triedenie nesmie nikdy spomaliť.
Pamäť: koľko pamäte navyše treba okrem zoznamu. 1 znamená pár premenných, n kópiu zoznamu.
Stabilný: dve rovnaké hodnoty si zachovajú pôvodné poradie. Dôležité pri triedení záznamov podľa jedného poľa.
Bez pamäte navyše: triedi priamo vnútri zoznamu, bez druhého zoznamu.
- porovnávanie
- presun
- na konečnom mieste
Dvojice v zlom poradí: 154 (na začiatku: 154) v zlom poradí zoradené Obe osi: hodnoty od najmenšej po najväčšiu
Stlačte Prehrať: čiary ukazujú, ako počas triedenia rastú náklady
Stlačte Prehrať alebo prechádzajte algoritmus krok po kroku.
Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.
Skúste: Zvoľte takmer zoradený zoznam. Po prechode bez jedinej výmeny algoritmus skončí skôr.
Ako to funguje
Porovnáva vždy dve susedné hodnoty a vymení ich, keď je ľavá väčšia. Najväčšia hodnota tak v každom prechode doputuje až na pravý koniec, ako bublina stúpajúca nahor. Ak prechod neurobí žiadnu výmenu, zoznam je už zoradený.
Kedy sa hodí
V skutočných programoch takmer nikdy, lebo na dlhých zoznamoch je pomalé. Na učenie je však výborné: ukazuje základnú myšlienku triedenia porovnávaním a vymieňaním. Rýchle je len na zozname, ktorý je už zoradený.