<< Inapoi la Metode de sortare

Sortare prin numarare

Sortarea prin numarare poate fi intalnita in doua variante:
1. Sortarea prin retinerea numarului de aparitii
2. Sortarea prin numararea elementelor si a elementelor mai mici

1. Sortare prin retinerea numarului de aparitii

Descrierea algoritmului
Sa presupunem ca avem un vector v, cu n elemente si stim ca acestea sunt intre valorile [a,b].
Algoritmul foloseste un vector caracteristic C, de aparitii, unde indicii reprezinta toate valorile <=b, insa in care vom folosi doar pe cele intre [a,b]. Initial este plin de 0.
Se parcurge vectorul v si pentru fiecare element v[i], vom creste valoarea C[v[i]] cu 1 (practic contorizam de cate ori apare v[i] in vectorul v).
La final parcurgem vectorul C si suprascriem vectorul v cu valorile din C (sau doar le afisam, in functie de problema).

Metoda este de complexitate liniara O(n), insa e important sa retinem particularitatile pe care trebuie sa le aiba sirul:
  • valorile din vectorul v sa fie de tipul ordinal;
  • valorile din vectorul v sa fie situate intr-un interval [a,b] relativ restrans (pentru ca vectorul C va avea b elemente). De exemplu daca vectorul v este format din numere cu cel mult 9 cifre, vectorul C ar trebui sa aiba un miliard de elemente si deci metoda nu e potrivita.
Exemplu:
Se citeste un sir din fisierul de intrare date.in. In fisier pot fi cel mult 1 milion de numere, iar valorile sunt numere cu cel mult 2 cifre. Sa se afiseze pe ecran elementele din fisier ordonate crescator.
Programul C++ este:

2. Sortare prin numararea aparitiilor si a elementelor mai mici

Descrierea algoritmului
Algoritm determina frecventa de aparitie a fiecarui element si in plus numara elementele mai mici. In acest fel se poate obtine, pentru fiecare element din tabloul nesortat, pozitia sa din tabloul sortat. Algoritmul are in vedere si situatia in care elementele se pot repeta.
Se vor folosi 3 tablouri:
  • Tabloul A - cel care trebuie sortat
  • Tabloul C - cel in care contorizam cate elemente sunt <= decat cel curent
  • Tabloul B - cel in care obtinem elementele sortate

Simularea metodei
Programul C++
#include <iostream>
using namespace std;
 
int main() {
    int A[20], B[20], n, i, j, C[101];
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>A[i];
 
    for (i=1; i<=100; i++) C[i]=0;
 
    for( j=1; j<=n; j++)
        C[A[j]]=C[A[j]] + 1;  //C[i] numara de cate ori apare A[j] (sau i) in vector
 
    for (i=2; i<=100; i++)
        C[i]=C[i] + C[i-1];   //C[i] va fi numarul elementelor mai mici sau egale cu i
 
    for(j=n; j>=1; j--){
        B[C[A[j]]]=A[j];
        C[A[j]]=C[A[j]] - 1;
    }
 
    for(i=1; i<=n; i++)
        cout<<B[i]<<" ";
 
    return 0;
}
 


.