Triedenie výberom
Nájde najmenšiu zo zostávajúcich hodnôt a vymení ju na ďalšie miesto. Výmen urobí veľmi málo, ale porovnaní vždy rovnaký počet.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- nie
- á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
- aktuálne minimum
- na konečnom mieste
Skúste: Zvoľte obrátený zoznam. Počet porovnaní zostane presne rovnaký ako pri akomkoľvek inom zozname.
Ako to funguje
Prejdite nezoradenú časť a nájdite v nej najmenšiu hodnotu. Vymeňte ju s prvou nezoradenou hodnotou, takže ďalšia hodnota je na konečnom mieste. Vždy sa kontrolujú všetky zostávajúce hodnoty, aj keď je zoznam už zoradený.
Kedy sa hodí
Hodí sa, keď je presúvanie dát drahé, ale čítanie lacné, lebo na každé miesto pripadá najviac jedna výmena. Inak je z jednoduchých metód zvyčajne lepšie triedenie vkladaním.