Heapsort
Usporiada zoznam do haldy, teda stromu, v ktorom je každý rodič väčší ako jeho potomkovia. Potom znova a znova presúva najväčšiu hodnotu na koniec.
- Ω(n log n)
- Θ(n log n)
- O(n log 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
- na konečnom mieste
Stlačte Prehrať: čiary ukazujú, ako počas triedenia rastú náklady
Stlačte Prehrať alebo prechádzajte algoritmus krok po kroku.
Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.
Skúste: Zvoľte obrátený zoznam. Stavba haldy takmer nepotrebuje výmeny, potom každé kolo presunie najväčšiu hodnotu na koniec.
Ako to funguje
Halda je uložená priamo v zozname. Hodnota na mieste s číslom i má potomkov na miestach 2i+1 a 2i+2 a najväčšia hodnota je vždy na začiatku. Vymeňte ju na koniec, zmenšite haldu o jedno miesto a opravte ju. Zoradená časť rastie sprava.
Kedy sa hodí
Keď potrebujete rýchlosť, ktorá vydrží aj v najhoršom prípade, a žiadnu pamäť navyše, napríklad na malých zariadeniach. V priemere je pomalší ako quicksort, preto často slúži len ako poistka.