Řazení výběrem

Najde nejmenší ze zbývajících hodnot a prohodí ji na další místo. Výměn udělá velmi málo, ale porovnání vždy stejný počet.

nejlepší Ω(n²)
průměrný Θ(n²)
nejhorší O(n²)
paměť O(1)
nestabilní
bez paměti navíc

Co to znamená?

Nejlepší případ: jak roste čas s velikostí seznamu n, když je vstup pro tento algoritmus nejsnazší.
Průměrný: obvyklý růst času s n. Při n² trvá dvakrát víc hodnot asi čtyřikrát déle; n log n roste mnohem pomaleji.
Nejhorší: růst času na nejtěžším vstupu. Důležitý, když se řazení nesmí nikdy zpomalit.
Paměť: kolik paměti navíc je potřeba kromě seznamu. 1 znamená pár proměnných, n kopii seznamu.
Stabilní: dvě stejné hodnoty si zachovají původní pořadí. Důležité při řazení záznamů podle jednoho pole.
Bez paměti navíc: řadí přímo uvnitř seznamu, bez druhého seznamu.

porovnávání
přesun
aktuální minimum
na konečném místě

0 / 399 kroků

Porovnání Výměny

Stiskněte Přehrát: čáry ukazují, jak během řazení rostou náklady

Rychlost 8 kroků/s

Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.

Zkuste: Zvolte obrácený seznam. Počet porovnání zůstane přesně stejný jako u jakéhokoli jiného seznamu.

Jak to funguje

Projděte neseřazenou část a najděte v ní nejmenší hodnotu. Prohoďte ji s první neseřazenou hodnotou, takže další hodnota je na konečném místě. Vždy se kontrolují všechny zbývající hodnoty, i když je seznam už seřazený.

Kdy se hodí

Hodí se, když je přesouvání dat drahé, ale čtení levné, protože na každé místo připadá nejvýše jedna výměna. Jinak je z jednoduchých metod obvykle lepší řazení vkládáním.