Sortarea prin numărare (Counting Sort) este o metodă de sortare a vectorilor ce se bazează pe utilizarea unui vector de frecvență. Acest algoritm de sortare poate fi extrem de eficient în anumite situații, în funcție de intervalul de valori al elementelor vectorului. Vom considera că vrem să sortăm un vector v, de lungime n, indexat de la 1 și cu elementele cuprinse între 0 și DMAX - 1.

Algoritm

Se parcurge vectorul v și se rețin frecvențele elementelor sale în vectorul de frecvență frq. Apoi, se parcurge vectorul frq de la 0 la DMAX - 1 dacă vrem să realizăm o sortare crescătoare, sau de la DMAX - 1 la 0 în caz contrar. Considerăm k noua lungime a vectorului, și o inițializăm cu 1. Pentru fiecare element frq[i], adăugăm valoarea i la finalul vectorului (pe poziția k, ce urmează a fi incrementată) de frq[i] ori, pentru că de atâtea ori apare aceasta în v. Ordinea în care este parcurs vectorul de frecvență ne garantează că elementele vor fi reintroduse în vector gata sortate.

Exemplu

Am notat vectorul inițial cu v, vectorul sortat cu w, iar vectorul de frecvență cu frq:

Exemplu: Sortare prin numărare

Implementare în C++

Mai jos este implementarea algoritmului în C++. Nimic special… Am declarat un iterator i pentru parcurgerea vectorilor și o variabilă k, cu semnificația de mai sus. Am parcurs v de la 1 la n, și am actualizat frecvența (numărul de apariții) ale elementului curent (v[i]) prin frq[v[i]]++. Apoi, l-am parcurs pe frq de la 0 la DMAX - 1 (pentru că ăsta e intervalul de valori al elementelor lui v). Pentru fiecare element frq[i], cât timp e nenul, îl decrementez, incrementez noul capăt al lui v (k), și îl copiez acolo pe i.

Se observă că sortarea prin numărare nu este un algoritm de sortare prin comparare, deoarece nu se efectuează nicio comparație între elementele vectorului. Soluția poate fi adaptată și pentru cazul în care intervalul de valori al lui v conține și numere negative, așa cum am descris în articolul Vectori caracteristici. Vectori de frecvență.

În plus, dacă nu avem nevoie de forma inițială a vectorului (cea nesortată), putem calcula frecvențele încă din timpul citirii vectorului. De asemenea, dacă nu trebuie decât să afișăm vectorul sortat, putem afișa elementele direct în while, fără să mai reconstruim vectorul. Iată mai jos o sursă completă care citește un șir de numere, și le afișează în ordine crescătoare, folosind sortarea prin numărare.

Complexitate

Sortarea prin numărare face 2 * n + DMAX pași. Un n de la parcurgerea lui v, un DMAX de la parcurgerea lui frq, și încă un n de la reintroducerea elementelor în v. Asta înseamnă o complexitate liniară, de ordinul $O(n + DMAX)$. Complexitatea spațiului auxiliar este $O(DMAX)$, pentru că este necesar un vector de frecvență de lungime DMAX.

Totuși, deși complexitatea algoritmului este liniară, acesta nu este fezabil în orice condiții. El este eficient doar când lungimea intervalului de valori ale elementelor din vector este suficient de mică în raport cu lungimea vectorului. Mai exact, sortarea prin numărare bate un algoritm de complexitate $O(n \log_2 n)$, cum ar fi QuickSort, atunci când $DMAX < n \log_2 n$. Similar, sortarea prin numărare e mai bună decât un algoritm în $O(n^2)$, ca sortarea prin selecție, când $DMAX < n^2$.

Dacă aveți vreo întrebare despre metoda sortării prin numărare, nu ezitați să o adresați mai jos printr-un comentariu 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!