Sortarea prin ansamble
Sortarea prin ansamble este sortarea prin selecție cu o metodă mai bună de a găsi cea mai mare valoare. Ea ține valorile nesortate într-un ansamblu, un arbore stocat chiar în listă, unde cea mai mare valoare e mereu în vârf. Scoaterea ei și refacerea ansamblului iau aproximativ log n pași în loc de o parcurgere completă.
Un arbore într-o listă
Un ansamblu binar este un arbore care nu are nevoie de pointeri. Poziția 0 este rădăcina, iar copiii poziției i sunt pozițiile 2i + 1 și 2i + 2, deci pozițiile 1 și 2 sunt copiii rădăcinii, pozițiile de la 3 la 6 sunt nivelul următor și așa mai departe. Fiecare nivel este plin, cu excepția ultimului, care se umple de la stânga. Într-un ansamblu max fiecare părinte este cel puțin la fel de mare ca copiii săi, deci cea mai mare valoare e mereu în rădăcină.
Coborârea
O singură operație face toată munca. Ca să coborâți o valoare, comparați-o cu copiii ei. Dacă cel mai mare copil e mai mare decât valoarea, se interschimbă, iar valoarea e comparată cu noii ei copii. Se oprește când niciun copil nu e mai mare sau când ajunge la bază. Cum arborele are doar aproximativ log₂ n niveluri, o coborâre face cel mult aproximativ 2 log₂ n comparații.
Mai întâi ansamblul, apoi sortarea
Ca să construiți ansamblul, coborâți fiecare părinte, de la ultimul înapoi la rădăcină. Fiecare subarbore e deja un ansamblu înainte ca părintele lui să coboare în el. Apoi sortați: interschimbați rădăcina, cea mai mare valoare, cu ultima valoare din ansamblu. Acea valoare e acum pe locul final. Ansamblul e mai scurt cu unu, iar valoarea ajunsă în rădăcină coboară ca să-l refacă. Repetați până rămâne o singură valoare.
Un exemplu
Luați 5, 1, 4, 2, 8. Construirea ansamblului coboară 1 sub 8, apoi 5 sub 8, ceea ce dă 8, 5, 4, 2, 1. Acum 8 trece la final; 1 ajunge în rădăcină și coboară sub 5 și 2: 5, 2, 4, 1 | 8. Apoi 5 trece la final, iar 1 coboară sub 4: 4, 2, 1 | 5, 8. Încă două runde termină lista: 1, 2, 4, 5, 8, după 12 comparații și 10 interschimbări.
Puncte forte și puncte slabe
Sortarea prin ansamble durează un timp proporțional cu n log n chiar și în cel mai rău caz și nu are nevoie de memorie suplimentară. Quicksort poate încetini până la n², iar sortarea prin interclasare are nevoie de o zonă tampon cât lista, așa că heapsort e varianta sigură de rezervă: introsort, folosit de biblioteca standard C++, trece la ea când partițiile din quicksort merg prost. Pe calculatoarele reale e de obicei mai lentă decât ambele, pentru că sare între locuri îndepărtate din listă, și nu este stabilă. J. W. J. Williams a publicat heapsort, împreună cu ansamblul binar, în 1964.
Explorați
Deschideți aplicația și apăsați Pas. Arborele de deasupra barelor arată ansamblul: valoarea care coboară are propria culoare, copilul cu care e comparată e evidențiat, iar fiecare interschimbare se vede atât în arbore, cât și în bare. După ce ansamblul e construit, urmăriți cum rădăcina trece la final, devine verde și iese din arbore.
Întrebări frecvente
Care este complexitatea în timp a sortării prin ansamble?
O(n log n) în cel mai bun caz, în cazul mediu și în cel mai rău caz. Construirea ansamblului durează O(n), iar fiecare dintre cele n − 1 extrageri durează O(log n). Sortează pe loc, cu O(1) memorie suplimentară.
Care este diferența dintre sortarea prin ansamble și sortarea prin selecție?
Ambele iau iar și iar cea mai mare (sau cea mai mică) valoare rămasă. Sortarea prin selecție o găsește parcurgând toată partea nesortată, n comparații de fiecare dată. Sortarea prin ansamble ține partea nesortată într-un ansamblu, unde cea mai mare valoare e deja în vârf, iar refacerea ansamblului costă doar aproximativ log n comparații.
La ce se mai folosește un ansamblu, în afară de sortare?
La cozi cu priorități: un ansamblu dă imediat cel mai mare (sau cel mai mic) element și permite adăugarea sau eliminarea elementelor în aproximativ log n pași. Planificatoarele, algoritmul lui Dijkstra pentru drumul cel mai scurt și simulările de evenimente folosesc toate unul.
Este sortarea prin ansamble stabilă?
Nu. Mutarea rădăcinii la final duce valorile pe distanțe mari, așa că valorile egale își pot schimba ordinea între ele.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați sortarea prin ansamble