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.

cel mai bun caz Ω(n log n)
caz mediu Θ(n log n)
cel mai rău caz O(n log n)
memorie O(1)
instabil
fără memorie suplimentară

Ce înseamnă acești termeni?

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ă

0 / 299 pași

Comparații Schimbări

Apasă pe redare: liniile arată cum crește costul în timpul sortării

Viteză 8 pași/s

Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.

Î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ță.