Sortarea tablourilor folosind coada de prioritati

Coada de prioritati poate fi folosita pentru a sorta un tablou. In acest scop, se pun elementele tabloului in coada de prioritati, in ordinea crescatoare a indicilor tabloului, apoi se extrag din aceasta si se pun in tablou, in ordinea inversa a indicilor. Daca se considera ca cel mai mare element are prioritate maxima, se obtine un tablou sortat crescator. In caz contrar, tabloul va fi sortat descrescator.

In cazul general, aceasta metoda de sortare necesita un spatiu de memorie suplimentar pentru coada de prioritati, egal cu lungimea tabloului care trebuie sortat. Daca, insa, se foloseste drept coada de prioritati un arbore de selectie, este posibil ca toate operatiile sa se faca in tabloul initial, fara a se cere memorie suplimentara. Se obtine astfel metoda de sortare HeapSort.
 

Metoda HeapSort (sortarea cu arbore de selectie)

Ideea de baza a metodei HeapSort este ca, pe masura ce elementele sunt scoase din tabloul de sortat si puse in coada de prioritati, spatiul ramas liber in tabloul de sortat este ocupat chiar de catre tabloul de selectie, ca in figura 14.


- Figura 14 -

Fie t tabloul care trebuie sortat, de lungime n.

Intr-o prima etapa, elementele sunt extrase din tabloul t in ordinea t[1], t[2], ... t[n-1] si puse in tabloul de selectie. Daca s-au extras deja k elemente din tablou si au fost puse in arborele de selectie, atunci zona t[0],...,t[k-1] este folosita pentru tabloul de selectie, iar zona t[k],...,t[n-1] este ocupata de elementele din t ramase inca pe vechile pozitii. La sfarsitul primei etape, intregul tablou t s-a transformat in arbore de selectie.

In a doua etapa a sortarii, elementele sunt extrase pe rand din tabloul de selectie si repuse in tabloul t. La extragerea elementelor din tabloul de selectie, acestea sunt scoase in ordinea prioritatii, iar tabloul de selectie se scurteaza. In spatiul ramas liber, se pun elementele extrase: primul element extras (cel de prioritate maxima) va fi pus pe pozitia t[n-1], al doilea pe pozitia t[n-2] etc. In final, intregul tablou t contine elementele sortate in ordine crescatoare a prioritatii, iar arborele de selectie este vid.

Avand in vedere ca punerea sau extragerea unui element din tabloul de selectie are complexitatea O(log n), iar in total se pun/extrag n elemente, complexitatea sortarii prin metoda HeapSort este O(n.log n).

Exemplu: In fisierul HeapSort.java este dat un exemplu de clasa care contine metoda statica
    public static void sort(double[] t)
care sorteaza prin metoda HeapSort tabloul t cu componente de tip double. Algoritmii folositi pentru punerea unui element in arborele de selectie sau pentru extragerea unui element sunt aceiasi ca cei folositi in metodele put si remove ale clasei ArboreSelectie. Un exemplu simplu de utilizare a clasei HeapSort pentru sortarea unui tablou este dat in fisierul TestHeapSort.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati