Sortarea tablourilor folosind coada de priorități

Coada de priorități poate fi folosită pentru a sorta un tablou. În acest scop, se pun elementele tabloului în coada de priorități, în ordinea crescătoare a indicilor tabloului, apoi se extrag din aceasta și se pun în tablou, în ordinea inversă a indicilor. Dacă se consideră că cel mai mare element are prioritate maximă, se obține un tablou sortat crescător. În caz contrar, tabloul va fi sortat descrescător.

În cazul general, această metodă de sortare necesită un spațiu de memorie suplimentar pentru coada de priorităti, egal cu lungimea tabloului care trebuie sortat. Dacă, însă, se folosește drept coadă de priorități un arbore de selecție, este posibil ca toate operațiile să se facă în tabloul inițial, fără a se cere memorie suplimentară. Se obține astfel metoda de sortare HeapSort.
 

Metoda HeapSort (sortarea cu arbore de selecție)

Ideea de bază a metodei HeapSort este că, pe măsură ce elementele sunt scoase din tabloul de sortat și puse în coada de priorități, spațiul rămas liber în tabloul de sortat este ocupat chiar de către tabloul de selecție, ca în figura 14.


- Figura 14 -

Fie t tabloul care trebuie sortat, de lungime n.

Într-o prima etapă, elementele sunt extrase din tabloul t in ordinea t[1], t[2], ... t[n-1] și puse în tabloul de selecție. Dacă s-au extras deja k elemente din tablou și au fost puse în arborele de selectie, atunci zona t[0],...,t[k-1] este folosită pentru tabloul de selecție, iar zona t[k],...,t[n-1] este ocupată de elementele din t ramase încă pe vechile poziții. La sfârșitul primei etape, întregul tablou t s-a transformat în arbore de selectie.

În a doua etapă a sortării, elementele sunt extrase pe rând din tabloul de selecție și repuse în tabloul t. La extragerea elementelor din tabloul de selecție, acestea sunt scoase în ordinea priorității, iar tabloul de selecție se scurtează. În spațiul rămas liber, se pun elementele extrase: primul element extras (cel de prioritate maximă) va fi pus pe pozitia t[n-1], al doilea pe pozitia t[n-2] etc. În final, întregul tablou t conține elementele sortate în ordine crescătoare a priorității, iar arborele de selecție este vid.

Având în vedere că punerea sau extragerea unui element din tabloul de selecție are complexitatea O(log n), iar in total se pun/extrag n elemente, complexitatea sortării prin metoda HeapSort este O(n.log n).

Exemplu: În fișierul HeapSort.java este dat un exemplu de clasă care conține metoda statică
    public static void sort(double[] t)
care sortează prin metoda HeapSort tabloul t cu componente de tip double. Algoritmii folosiți pentru punerea unui element în arborele de selecție sau pentru extragerea unui element sunt aceiași ca cei folosiți în metodele put și remove ale clasei ArboreSelectie. Un exemplu simplu de utilizare a clasei HeapSort pentru sortarea unui tablou este dat în fișierul TestHeapSort.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați