Comparatie intre diferite tipuri de sortari avansate. - Count Sort.

Breviar teoretic
BrickSort
BucketSort
CountSort
RadixSort
Bibliografie
Concluzii
Contactati-ma !

        Pentru inceput, o scurta prezentare teoretica: dupa cum ii si spune numele, CountSort realizeaza sortarea prin numarare. Este oare vreo contradictie? Adica se pot sorta elemente doar numarandu-le? Raspunsul este afirmativ si iata de ce: sa introducem restrictia: avem de sortat un vector V despre care se cunoaste faptul ca toate elementele sale (sa zicem 8) sunt situate intre -3 si 20. Iata cum vom proceda: mai construim un vector TEMP (vector temporar) cu 24 de pozitii, astfel pe pozitia TEMP[0] vom memora cate elemente cu valoarea -3 avem in vectorul V, pe pozitia TEMP[1] vom memora cate elemente din V sunt -2, si tot asa mai departe, pe pozitia TEMP[23] vom memora cate elemente din V au valoarea 20. Initializam tot vectorul TEMP cu 0 (pe toate pozitiile). Sortarea decurge astfel: parcurgem vectorul V si pentru fiecare valoare din V, incrementam contorul corespunzator in vectorul TEMP. De exemplu, daca V[]={1,1,4,1,2,3,8,20}, atunci V[0]=1 si in TEMP pe pozitia corespunzatoare valorii 1, adica in TEMP[4], gasim 0. Incrementam valoarea si TEMP[4]=1. Apoi V[1]=1, pe pozitia TEMP[4]=1 si incrementam TEMP[4]=2. V[2]=4 si in TEMP[7] (pe pozitia corespunzatoare valorii 4) gasim 0 pe care il incrementam, deci TEMP[7]=1. Apoi V[3]=1 si incrementam TEMP[4] la 3. Algoritmul se opreste la terminarea lui V. Cum se vor afisa rezultatele? Iata: parcurgem vectorul TEMP si afisam ce gasim in el: pozitia TEMP[0] corespunde valorilor -3 din V. La TEMP[0] gasim 0, deci in V se afla 0 valori -3. Apoi in TEMP[1] pentru -2, tot 0. In TEMP[2] pentru -1, tot 0 valori; in TEMP[3] pentru 0 gasim tot 0. La TEMP[4] (corespunzatoare valorii 1) gasim 3, deci in V se afla 3 valori 1. Si asa mai departe pana la epuizarea lui TEMP. Hai sa studiem complexitatea algoritmului: aparent ea este direct proportionala cu numarul de pozitii din V, deci C=O(n). Acest lucru este insa aparent pentru ca in O(n) se face numai numararea. Aflarea rezultatelor se realizeaza parcurgand vectorul TEMP care are maxim(V)-minim(V) elemente. (Am notat prin maxim(V) valoarea maxima din V si prin minim(V) valoarea minima din V). Asadar pentru aflarea rezultatelor, algoritmul are o complexitate C=O(n*(maxim(V)-minim(V))). Daca valorile maxime si minime din V nu se cunosc, mai e necesara o parcurgere a lui V. Asadar, complexitatea devine C=O(n²*(maxim(V)-minim(V))). Daca intre valoarea maxima si minima din V este o diferenta mare, atunci algoritmul devine foarte costisitor din punct de vedere al costului de memorie si complexitatii. Deci acest algoritm nu este o solutie, ci numai o justificare a faptului ca este posibila o sortare prin numarare.
        Ceea ce retinem din justificarea de mai sus este faptul ca: intr-o multime formata cu elementele unui vector, pozitia finala a unui element din multime este egala cu numarul de elemente mai mici decat el.
        Bazati pe cele de mai sus putem construi un algoritm astfel (aloritm in pseudocod):

CountSort(int V[])
   {pentru(i<-0;i<NumarElementePosibile;i<-i+1) executa:
     pentru(j<-i+1;j<NumarElementePosibile;j<-j+1) executa:
       daca(V[i]>V[j]) atunci pozitie[i]<-pozitie[i]+1;
       altfel pozitie[j]<-pozitie[j]+1;
   pentru(i<-0;i<lungime(V);i<-i+1) executa: TEMP[pozitie[i]]<-V[i];
   pentru(i<-0;i<lungime(V);i<-i+1) executa: V[i]<-TEMP[i].
   }
   GATA !

        Codul algoritmului CountSort in C++ parametrizat se afla aici
        Codul algoritmului CountSort in J++ se afla aici

        Corectitudinea algoritmului este urmatoarea: in secventa sortata vor aparea in fata fiecaruia dintre elemente exact acele elemente mai mici decat el (pentru ca secventa este sortata); asadar pozitia finala a unui element in vectorul sortat este egala cu numarul de elemente din multime mai mici sau egale cu el. In algoritm se determina numarul de elemente mai mici sau egale cu elementul curent, adica pozitia in vectorul sortat.

Complexitatea algoritmului se calculeaza direct si simplu din algoritmul in pseudocod. Complexitatea este dependenta de "gradul de sortare" (adica cu cat elementele sunt mai sortate in vectorul initial V, cu atat complexitatea scade) al vectorului initial. C=1 + 2 + 3 + ... + (n-1) + n=^n*(n-1)/₂. Asadar, complexitatea este: O(n²).

Pentru a rula pagina la inceput (la meniu) dati un click aici.