Heapsort
Aranjează lista într-un heap, un arbore în care fiecare părinte e mai mare decât copiii lui. Apoi mută cea mai mare valoare la capăt, iar și iar.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- nu
- da
Cel mai bun caz: cum crește timpul cu mărimea n a listei când intrarea e cea mai ușoară pentru acest algoritm.
Caz mediu: creșterea obișnuită a timpului. La n², de două ori mai multe valori cer cam de patru ori mai mult timp; n log n crește mai lent.
Cel mai rău caz: creșterea pe intrarea cea mai grea. Util când viteza nu are voie să scadă niciodată.
Memorie: câtă memorie suplimentară e necesară pe lângă listă. 1 înseamnă câteva variabile, n înseamnă o copie a listei.
Stabil: două valori egale își păstrează ordinea inițială. Contează când sortezi după un singur câmp al unei înregistrări.
Fără memorie suplimentară: sortează chiar în listă, fără o a doua listă.
- comparare
- mutare
- pe poziția finală
Încearcă: Alege o listă inversată. Heap-ul se construiește aproape fără schimbări, apoi fiecare rundă mută cea mai mare valoare la capăt.
Cum funcționează
Heap-ul e ținut chiar în listă: valoarea de pe poziția i are copiii pe pozițiile 2i+1 și 2i+2, iar cea mai mare valoare e mereu în față. O muți la capăt printr-o schimbare, micșorezi heap-ul cu o poziție și îl repari. Partea sortată crește dinspre dreapta.
Când este o alegere bună
Când ai nevoie de o viteză care rămâne bună chiar și în cel mai rău caz, fără memorie suplimentară, de exemplu pe dispozitive mici. În medie e mai lent decât quicksort, așa că e folosit des ca plasă de siguranță.