Triedenie zlučovaním
Rozdelí zoznam na polovice, každú polovicu zoradí a potom obe polovice zlúči do jedného zoradeného zoznamu.
- najlepší Ω(n log n)
- priemerný Θ(n log n)
- najhorší O(n log n)
- pamäť O(n)
- stabilný
- potrebuje pamäť navyše
Čo to znamená?
- 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
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 zoznam s málo rôznymi hodnotami. Z dvoch rovnakých hodnôt sa najprv vezme tá z ľavej polovice, takže rovnaké hodnoty držia poradie.
Ako to funguje
Delte zoznam, kým v každom kúsku nezostane jediná hodnota. Taký kúsok je už zoradený. Potom kúsky zlučujte po dvojiciach: porovnajte prvé hodnoty oboch kúskov a vezmite menšiu, znova a znova. Zdvihnutý rad v animácii je pamäť navyše, ktorú zlučovanie potrebuje.
Kedy sa hodí
Keď potrebujete rýchlosť, ktorá vydrží aj v najhoršom prípade, a rovnaké hodnoty si musia zachovať poradie. Python aj Java používajú jednu z verzií triedenia zlučovaním. Nevýhodou je pamäť navyše, ktorú potrebuje.