Triedenie vkladaním
Po jednej hodnote buduje vľavo zoradenú časť. Každú novú hodnotu vyberie a posúva doľava, kým nenarazí na menšiu hodnotu.
- najlepší Ω(n)
- priemerný Θ(n²)
- najhorší O(n²)
- pamäť O(1)
- stabilný
- bez pamäte 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
- v ruke
- zoradená časť
- 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 takmer zoradený zoznam. Takmer nič sa neposúva, takže triedenie skončí po veľmi malom počte krokov.
Ako to funguje
Ľavá časť je vždy zoradená. Vyberte ďalšiu hodnotu a každú väčšiu hodnotu v zoradenej časti posuňte o jedno miesto doprava. Potom vložte vybranú hodnotu do vzniknutej medzery. Takto si veľa ľudí triedi karty v ruke.
Kedy sa hodí
Dobrá voľba pre krátke zoznamy a pre zoznamy, ktoré sú takmer zoradené - tam je veľmi rýchle. Knižnice na triedenie ho v praxi používajú vnútri rýchlejších metód na malé kúsky zoznamu.