Řazení vkládáním
Po jedné hodnotě buduje vlevo seřazenou část. Každou novou hodnotu vyjme a posouvá doleva, dokud nenarazí na menší hodnotu.
- nejlepší Ω(n)
- průměrný Θ(n²)
- nejhorší O(n²)
- paměť O(1)
- stabilní
- 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
- v ruce
- seřazená část
- na konečném místě
Stiskněte Přehrát: čáry ukazují, jak během řazení rostou náklady
Stiskněte Přehrát nebo procházejte algoritmus krok po kroku.
Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.
Zkuste: Zvolte téměř seřazený seznam. Skoro nic se neposouvá, takže řazení skončí po velmi malém počtu kroků.
Jak to funguje
Levá část je vždy seřazená. Vyjměte další hodnotu a každou větší hodnotu v seřazené části posuňte o jedno místo doprava. Pak vložte vyjmutou hodnotu do vzniklé mezery. Takhle si mnoho lidí řadí karty v ruce.
Kdy se hodí
Dobrá volba pro krátké seznamy a pro seznamy, které jsou skoro seřazené - tam je velmi rychlé. Knihovny pro řazení ho v praxi používají uvnitř rychlejších metod na malé kousky seznamu.