|
|
|
Vectori ordonati
Un vector ordonat reduce timpul anumitor operatii, cum ar fi: cautarea unei valori date, verificarea unicitatii elementelor, gasirea perechii celei mai apropiate, calculul frecventei de aparitie a fiecarei valori distincte s.a.
Un vector ordonat poate fi folosit si drept coada cu prioritati, daca nu se mai fac adaugari de elemente la coada, pentru ca valoarea minima (sau maxima) se afla la una din extremitatile vectorului, de unde se poate scoate fara alte operatii auxiliare.
Mentinerea unui vector in ordine dupa fiecare operatie de adaugare sau de stergere nu este eficienta si nici nu este necesara de multe ori; atunci cand avem nevoie de o colectie dinamica permanent ordonata vom folosi un arbore binar sau o lista inlantuita ordonata. Ordonarea vectorilor se face atunci cand este necesar, de exemplu pentru afisarea elementelor sortate dupa o anumita cheie.
Pe de alta parte, operatia de sortare este eficienta numai pe vectori; nu se sorteaza liste inlantuite sau arbori neordonati sau tabele de dispersie.
Sunt cunoscuti mai multi algoritmi de sortare, care difera atat prin modul de lucru cat si prin performantele lor. Cei mai simpli si ineficienti algoritmi de sortare au o complexitate de ordinul O(n*n), iar cei mai buni algoritmi de sortare necesita pentru cazul mediu un timp de ordinul O(n*log2n), unde "n" este dimensiunea vectorului.
Uneori ne intereseaza un algoritm de sortare "stabila", care patreaza ordinea initiala a valorilor egale din vectorul sortat. Mai multi algoritmi nu sunt "stabili".
De obicei ne intereseaza algoritmii de sortare "pe loc", care nu necesita memorie suplimentara, desi exista cativa algoritmi foarte buni care nu sunt de acest tip: sortare prin interclasare si sortare prin distributie pe compartimente.
Algoritmii de sortare "pe loc" a unui vector se bazeaza pe compararea de elemente din vector, urmata eventual de schimbarea intre ele a elementelor comparate pentru a respecta conditia ca orice element sa fie mai mare ca cele precedente si mai mic ca cele care-i urmeaza.
Vom nota cu T tipul elementelor din vector, tip care suporta comparatia prin operatori ai limbajului (deci un tip numeric). In cazul altor tipuri (structuri, siruri) se vor inlocui operatorii de comparatie (si de atribuire) cu functii pentru aceste operatii.
Vom defini mai intai o functie care schimba intre ele elementele din doua pozitii date ale unui vector:
void swap (T a[ ], int i, int j)
Vom prezenta aici cativa algoritmi usor de programat, chiar daca nu au cele mai bune performante.
Sortarea prin metoda bulelor ("Bubble Sort") compara mereu elemente vecine; dupa ce se compara toate perechile vecine (de la prima catre ultima) se coboara valoarea maxima la sfarsitul vectorului. La urmatoarele parcurgeri se reduce treptat dimensiunea vectorului, prin eliminarea valorilor finale (deja sortate). Daca se compara perechile de elemente vecine de la ultima catre prima, atunci se aduce in prima pozitie valoarea minima, si apoi se modifica indicele de inceput. Una din variantele posibile de implementare a acestei metode este functia urmatoare:
void bubbleSort(T a[ ], int n)
Timpul de sortare prin metoda bulelor este proportional cu patratul dimensiunii vectorului (complexitatea algoritmului este de ordinul n*n).
Sortarea prin selectie determina in mod repetat elementul minim dintre toate care urmeaza unui element a[i] si il aduce in pozitia i, dupa care creste pe i.
void selSort( T a[ ], int n)
Sortarea prin selectie are si ea complexitatea O(n*n), dar in medie este mai rapida decat sortarea prin metoda bulelor (constanta care inmulteste pe n*n este mai mica).
Sortarea prin insertie considera vectorul format dintr-o partitie sortata (la inceput de exemplu) si o partitie nesortata; la fiecare pas se alege un element din partitia nesortata si se insereaza in locul corespunzator din partitia sortata, dupa deplasarea in jos a unor elemente pentru a crea loc de insertie.
void insSort (T a[ ], int n)
a[j+1]=x; // muta pe x in pozitia j+1
}
Nici sortarea prin insertie nu este mai buna de O(n*n) pentru cazul mediu si cel mai nefavorabil, dar poate fi imbunatatita prin modificarea distantei dintre elementele comparate. Metoda cu increment variabil (ShellSort) se bazeaza pe ideea (folosita si in sortarea rapida QuickSort) ca sunt preferabile schimbari intre elemente aflate la distanta mai mare in loc de schimbari intre elemente vecine; in felul acesta valori mari aflate initial la inceputul vectorului ajung mai repede in pozitiile finale, de la sfarsitul vectorului.
Algoritmul lui Shell are in cazul mediu complexitatea de ordinul n1.25 si in cazul cel mai rau O(n1.5), fata de O(n2) pentru sortare prin insertie cu pas 1.
In functia urmatoare se folosesc rezultatele unor studii pentru determinarea valorii initiale a pasului h, care scade apoi prin impartire succesiva la De exemplu, pentru n > 100 pasii folositi vor fi 13,4 si 1.
void shellSort(T a[ ], int n)
// sortare prin insertie cu increment h variabil
while (h > 0)
h /= 3; // urmatorul increment
}
