Heapsort
Uspořádá seznam do haldy, tedy stromu, ve kterém je každý rodič větší než jeho potomci. Pak znovu a znovu přesouvá největší hodnotu na konec.
- nejlepší Ω(n log n)
- průměrný Θ(n log n)
- nejhorší O(n log 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
- 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 obrácený seznam. Stavba haldy skoro nepotřebuje výměny, pak každé kolo přesune největší hodnotu na konec.
Jak to funguje
Halda je uložená přímo v seznamu. Hodnota na místě s číslem i má potomky na místech 2i+1 a 2i+2 a největší hodnota je vždy na začátku. Prohoďte ji na konec, zmenšete haldu o jedno místo a opravte ji. Seřazená část roste zprava.
Kdy se hodí
Když potřebujete rychlost, která vydrží i v nejhorším případě, a žádnou paměť navíc, třeba na malých zařízeních. V průměru je pomalejší než quicksort, proto často slouží jen jako pojistka.