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.

najlepší Ω(n²)
priemerný Θ(n²)
najhorší O(n²)
pamäť O(1)
nestabilný
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
aktuálne minimum
na konečnom mieste

0 / 399 krokov

Porovnania Výmeny

Stlačte Prehrať: čiary ukazujú, ako počas triedenia rastú náklady

Rýchlosť 8 krokov/s

Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.

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.