| Hemorrhoid pain relief

Algoritmi.

Prezentarea algoritmului de sortare prin ansamble (heapsort).

Cuprins:
1. Definirea sortarii prin ansamble (heapsort).
2. Varinate ale sortarii prin ansamble.
3. O comparatie a algoritmului de sortare prin ansamble cu alte metode de sortare.
4. Pseudocodul algoritmului de sortare prin ansamble exprimat in limabjul Pascal.
5. Un exemplu complet de algoritm de sortare prin ansamble.





1. Definirea sortarii prin ansamble. >>>

Sortarea prin ansamble (sau "heapsort") este unul dintre cei mai buni algoritmi de sortare, de comparare si face parte din familia algoritmilor de sortare prin selectie.Desi are o performanta mai scazuta decat cele mai bune implementari ale sortarii rapide, el are totusi avantajul de a realiza o sotare dificila intr-un timp de O(n logn).Sortarea prin ansamble este un algoritm de sortare "pe loc" si nu este un algoritm de sortare stabil.

Un mod simplu de a sorta o lista de elemente este utlilizarea structurii de date numita heap (in traducere inseamna "gramada ordonata").Adica toate elementele care trebuiesc sortate sunt inserata intr-o gramada ordonata de elemente, si aceasta gramada ordonata de elemente este organizata in asa mod incat fiecare dintre elementele cu valori mari (se adauga in gramada elementelor cu valori mari) iar elementele cu valori mai mici (se adauga in gramada elementelor cu valori mici) pentru ca ele sa fie usor de extras.Oricum, acest mod de aranjare a elementelor aranjeaza structura gramezii de elemente ordonate, aceste elemente cu valori mici sau mari pot fi extrase in mod repetat pana cand nu mai ramane nici un element in gramada.Extragerea elementelor se realizeaza in ordinea elementelor.

Daca se utlilizeaza acest mod de sortare atunci va fi necesara prezenta unui spatiu suplimentar de memorie pentru a stoca elementele grupate ordonat (heap).Un alt mod de a stoca eficient o grupare ordonata de elemente este utlilizarea stocarii binare (sau stocarea alternativa, adica sa se stocheze o gramada de elemente ordonate a carui structura (arbore) sa aiba mai mult de doi fii) in cadrul unui tablou de intrare care nu este inca sortat.Sortarea prin ansamble efectueaza doua operatii de baza asupra structurii arborelui al elementelor grupa ordonat: insertia si suprimarea nodului radacina.De fiecare data se va suprima (extrage) elementul cu cea mai mare valoare din gramada, apoi acesta se va pozitiona in ultimul loc al tabloului care nu este ocupata, si se utilizeaza acest principiu si pentru elementele ramase nesortate din tablou: Grupul elementelor ce trebuiesc sortate Elemente sortate

Sortarea unor elemente de diferite valori prin metoda sortarii prin ansamble.

2. Variante ale sortarii prin ansamble. >>>
* Cea mai importanta varianta a unui algoritm simplu de sortare prin ansamble a fost improvizat de catre R.W.Floyd care in practica este cu 25% mai rapid deoarece foloseste numai o comparatie la fiecare adaugare a unui element in gramada de elemente ordonate urmata apoi de stergerea nodului radacina (principal) pentru nodul-fiu nou adaugat.Astfel aceasta versiune de sortare prin ansamble lucreaza mult mai usor, caci metoda originala a sortarii prin anamble realizeaza o localizare crescatoare a elementelor.Astfel ca metoda lui R.W.Floyd incepe sortarea de la adresa elementului care a fost inlocuit, astfel ca algoritmul care functiioneaza dupa acest principiu va avea +/-1 contrabalansari in codul de implementare.

* O alta varianta a sortarii prin ansamble mai putin cunoscuta este sortare ternara prin ansamble care utlilizeaza o grupare termnara de elemente ordonate intr-un gup binar de elemente ordonate, adica fiecare element din gramada va avea teri fii.Sortarea elementelor ternare este mult mai complexa de programat insa este mult mai rapida, caci fiecare pas al metodei de inlocuire efectueaza trei comparatii apoi elementele sunt aranjate intr-o singur grup ternar ordonat de elemente, iar daca se utilizeaza un grup de elemente binare vor fi necesare doua comparatii pentru fiecare element care vor pi stocate intr-un griup de elemente ordonate.Sortarea elementelor ternare poate efectua doua comparatii intr-un timp mult mai scurt decat se compara trei elemente binare , insa aceste doua comparatii ale sortarii ternare multiplica numarul de noduri ale arborelui elementelor ternare cu un factor de 9, care este mai mult decat factorul de 8 pe care il detine arborele elementelor binare.Oricum, chiar daca sortarea ternara este mai greu de programat, ea este cu 12% mai rapida decat cea mai simpla varianta a sortarii prin ansamble.

* Algoritmul de sortare smoothsort (in taducere inseamna "sortarea in plan") este o alta varianta a sortarii prin ansamble descoperit de catre Edser Dijkstra in anul 1981.Aceasta varianta de sortare are si ea limita timpului de sortare de finit prin relatia O(n log n).Avantajul sortarii in plan este ca realizeaza un timp de sortare apropiat de limita de timnp definita prin realatia O(n) daca elementele ce trebuiesc sortare sunt sortare partial, iar sortarea prin ansable in acest caz realizeaza o limita a timpului de sortare definita prin realatia O(n log n).Sortarea in plan este rar utilizata deoarece prezinta un algoritm complex.

3. O comparatie a metodei de sortare prin ansamble cu alte metode de sortare. >>>
Sortarea pri ansamble ar putea concura cu sortarea rapida, care este un algoritm de sortare foarte eficient, si care este bazat pe procedeul de comparare a elementelor.

Sortarea rapida (quicksort) este tipic mult mai rapida deoarece poate accesa date stocate in memoria CACHE de unde se desprind si alte avantaje, insa timpul de sortare pentru acesta sortare rapida in cazul in care se comporta ineficient este de O(n²), care este inacceptabil daca se lucreaza cu lista mari de date, aceasta se poate intampla si daca nu se cunoaste foarte bina algoritmul de implementare, rezultand uneori si un risc de securitate.

Algoritmul de sortare rapida necesita un spatiu de memorie suplimantar care are un numar de Ω(log n) locatii, acasta insemnand ca nu este un algoritmde sortare "pe loc".Aceasta in general nu reprezinta un dezavantaj, insa poate fi in cazul in care este folosita in cadrul sistemelor bazate pe microprocesoare sau microcontrlolere unde daca alocarea memoriei este restrictionata.Este posibila si crearea de algoritmi de sortare rapida care sa utilizeze un spatiu de memorie care sa aiba in pemanent acelasi nu ar de locatii, insa aceasta este foarte rar utilizat in practica deoarece este un algoritm complex.

Sortarea prin ansamble este utilizata in carul sistemelor bazate pe microprocesoare sau microcontrolere care sunt restrictionate in rularea in timp real sau au restrictionat si spatiul de memorie alocat, ori sistemele trebuie sa aiba un grad mare de secutitate, deoarece realizeaza o limita a timpului in de sortare definit prin relatia O(n log n) avant si avantajul utliliozari unui spatiu auziliar de memorie constant.

Soartarea prin ansamble mai poate concura si cu sortarea prin interclasare, care este o metoda de sortare ce are aceasi limita a timpului de sortare ca si sortaea prin ansamble, insa sortarea prin interclasare necesita un spatiu de memorie suplimentara de Ω(n) locatii, insa sortarea prin ansamble utilizeaza un spatiu constant de memorie.Un alt avantaj al sortarii prin ansambel in comparatie cu sortarea prin inerclasare este ca se poate comporta eficient in practica, in cazul in care se utilizeaza echipamente mici si greu accesibile din memoria CACHE.Intr-o alta ordine de idei putem constata ca sortarea prin interclasare a re mai multe avantaje decat sortarea prin ansamble:

* Asemanator cu sortarea rapida, sortarea prin interclasare realizeaza o sortare rapida a elementelor greu accesibile din memoria CACHE, fiind astfel mult mai performante decat sortarea prin ansamble, deoarece acestea acceseaza elementele in ordinea in care sunt localizate.

* sortarea prin interclasare este o sortare stabila.

* Sortarea prin interclasare poate sorta in paralel, fara ca procesele de sortare sa depinda unele de altele, realizand astfel un timp de sortare liniar, insa acest concept nu poate fi pentru sortarea prin ansamble.

* Sortarea prin interclasare poate fi adaptata usor pentru a putea opera cu liste inlantuite sau cu liste de mari dimensiuni stocate pe dispozitive CD-ROM sau stocate intr-o locatie din retea care sunt accesate foarte lent.Sortarea prin ansamble se comporte aficient numai daca datele cu care lucreaza pot fi accesate aleator, insa cum acest tip de sortare prezinta o localizare a referintelor foarte slab rezulta ca aceasta s-ar comporta foarte ineficient in cazul in care se lucreaza cu dipozitive care necesita un timp oarecum mare de acces.


4. Pseudocod pentru sortarea prin ansamble exprimat in limbajul Pascal. >>>
Exemplul de algoritm prezentat mai jos este reprezinta un "simplu" mod de a implementa un algoritm de sortare prin ansamble, unde termenul de inlocuieste este folosit pentru a schimba pozitia pentru doua elemente aflate in tabloul care se sorteaza.

 function sortare_ansamble(a, contor) este
inceput:  un tablou in care elementele au ordine diferita a de lungime contor
( prima locatie a elementelor cu valori mari)
 grupeaza(a, contor)
capat := contor - 1
while capat > 0 do
(inlocuieste radacina (elementeul cu valoarea maxima) grupului cu ultimul element di grup)
inlocuieste(a[capat], a[0])
(se scade numarul de elemente din grupul care trebuie sortat cu 1, astfe incat radacina anterioara
este pozitionata in locatia protrivita)
caapt:= capat - 1
(se aranjeaza descrescator grupul de elemente iarasi dupa ordinea elementelor cu valori mari)
aranjeaza_descrescator(a, 0, capat)
function grupeaza(a,contor) este
(se incape prin a localiza pozitia parintelui ultimului nod din grup)
inceput := contor ÷ 2 - 1
while inceput >=  0 do
(inlocuieste nodul de la pozitia de la care se porneste sortarea in pozitia potrivita, 
 si se contiuna astfel pentru toate nodurile urmatoaare  conform ordinii pozitiilor elementelor din grup)
aranjeaza_descrescator(a, inceput, contor-1)
inceput := inceput - 1
(astfel radacina pentru toate nodurile si elementele sunt ordonate)/ul>function aranjeaza_descrescator(a, inceput, capat) este
intrare:  capat reprezinta pozitia ultimului element din grupul ce trebuie sortat
radacina := inceput
while radacina * 2 + 1 > = capat do
(atat timp cat radacina are un singur fiu)
fiu := radacina * 2 + 1 (radacina*2+1 este o referinta pentru fiul din stanga)
(Daca fiul mai are un frate si daca valoarea fiului este mai mica decat a fratelui...)
if fiu < capat and a[fiu] < a[fiu + 1] then
fiu := fiu + 1 (... atunci fa realizeaza o referinta  pentru fiul din dreapta)
if a[radacina] < a[fiu] then (se termina procedeul de ordoanre in functie de elementul cu valarea maxima)
inlocuieste(a[radacina], a[fiu])
radacina := fiu (se repeta procedeul de aranjarea a alementelor)
elsereturn

Functia grupeaza poate fi vazuta ca un procedeu recursiv de insearare a elementelor din grup intr-o ordine crescatoare.A doua versiune difera numai prin faptul ca datele se ordoeaza in ordinea in care sunt sortate.Meotoda de aranjeare de deasupra incepe sortarea de la capatul grupului (adica cu elementele care pot avea valori mari) si urca pe masura ce elementele sunt sortate.Urmaotrul algoritm incepe sortarea la inceputul grupului de elemente si coboara catre capatul grupului pe masura ce elementele sunt sortate in ordine crescatoare:

function grupeaza(a,contor) este
(capat este atribuit pentru elementul aflat pe pozitia prima pozitie,
 acesta find elementul stang al radacinii (val miinma a grupului))
capat := 1
while capat < contor
(aranjeaza cescator referinta aflata la inceputul grupului in locul potrivit,
procedand asa si pentru toate nodurile de deasupra 
aranjeaza_crescator(a, 0, capat)
capat := capat + 1
(dupa ce s-a aranjat crescator si ultimul nod, atunci grupul este sortat crescator)
function aranjeaza_crescator(a, incput, capat) este
inceput:  inceput reprezinta locatia primului element al grupului care trebuie sortat.
fiu := capat while fiu > inceput
parinte :=[(child - 1) ÷ 2]
if a[parinte] < a[fiu] then (se paraseste metoda de sortare in ordinea elementelor cu valori maxime)
inlocuieste(a[parinte], a[fiu])
fiu := parinte (se contiunea aranjarea crescatoare incpunad cu un nou nod parinte)
else
return

5. Exemplu de implementare in limbajul C al algoritmului de sortare prin ansamble. >>>


#include 
#include 
void sortare_ansamble(int[], int);
int main()
{
int i;
int a[] = {7,2,10,25,17,23,27,16,19,37,42,4,33,1};//copia tabloului care trebuie sortat
int a1[] = {7,2,10,25,17,23,27,16,19,37,42,4,33,1};//tabloul care trebuie sortat
for(i=sizeof(a)/sizeof(*a); i>1; i--)
{
sortare_ansamble(a, i - 1);
}
printf("Tabloul initial este: ");
 for(i=0;iprintf("\n");
printf("\nTabloul sortat este: ");
for (i = 0; i < sizeof(a)/sizeof(*a); i++)
printf(" %d ",a[i]);
return;
}
void sortare_ansamble(int a[], int limita_a)
{
int i,o;
int fiu_stang, fiu_drept, fiu_mijloc, radacina, temp;
radacina = (limita_a-1)/2;
for(o=radacina;o>=0;o--)
{
for(i=radacina;i>=0;i--)
{
fiu_stang = (2*i)+1;
fiu_drept = (2*i)+2;
if ((fiu_stang <= limita_a) && (fiu_drept <= limita_a))
{
if(a[fiu_drept] >= a[fiu_stang])
fiu_mijloc = fiu_drept;
else
fiu_mijloc = fiu_stang;
}
else
{
if(fiu_drept > limita_a)
fiu_mijloc = fiu_stang;
else
fiu_mijloc = fiu_drept;
}
if (a[i] < a[fiu_mijloc])
{
temp = a[i];
a[i] = a[fiu_mijloc];
a[fiu_mijloc] = temp;
}
}
}
temp = a[0];
a[0] = a[limita_a];
a[limita_a] = temp;
return; 
}

Exemplu de mai sus va afisa pe ecran:

Tabloul initial este:  7  2  10  25  17  23  27  16  19  37  42  4  33  1
Tabloul sortat este:  1  2  4  7  10  16  17  19  23  25  27  33  37  42 

Structuri de date abstracte | SDA Arbori | SDA Arbori Binari | SDA Arbori Multicai | SDA Arbori Optimi | SDA Graf | Traversarea grafurilor | SDA Graf Ponderat | SDA Graf Orientat | SDA Lista Inlantuita | SDA Tablou Asociat | Despre algoritmi. | Algoritmi de cautare neinformata, cautarea inforamata,cautarea in liste,in grafuri, in SQL-uri | Algoritmi de cautare liniara, binara, interpolare | Prezentare Algoritmi Sortare | Sortare Insertie cu Pas Variabil (Shellsort) | Sortarea Prin Ansamble (Heapsort) | Sortarea Prin Insertie (Insertionsort) | Sortarea Prin Interclasare (Mergesort) | Sortarea Prin Interschimbare (Bubblesort) | Sortarea Prin Selectie (Selectionsort) | Sortarea Rapida (Quicksort)

Inapoi la pagina principala