Sortare prin numărare

De ce contează?

Vrei să aranjezi crescător notele unei clase (de la 1 la 10). În loc să le compari între ele, faci altfel: numeri câți au luat 1, câți 2, câți 3... Apoi le „torni" înapoi în ordine. Ai sortat fără să compari nimic — doar numărând.

Ideea: sortare fără comparații

Sortările pătratice compară elemente. Sortarea prin numărare nu compară nimic: folosește un vector de frecvențe. frec[x] = de câte ori apare valoarea x. Apoi parcurgi valorile crescător și rescrii fiecare de câte ori apare.

Algoritm pas cu pas:

Numără aparițiile (valori 0..3):

frec	0	2	1	2
val	0	1	2	3

frec[1]=2, frec[2]=1, frec[3]=2: valoarea 1 apare de 2 ori, 2 o dată, 3 de 2 ori.

Parcurgi valorile crescător și rescrii: 1 (×2), 2 (×1), 3 (×2) → 1 1 2 3 3.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int v[1000];
    int valMax = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        if (v[i] > valMax) valMax = v[i];
    }

    int frec[1001] = {0};               // initializat cu 0
    for (int i = 0; i < n; i++) {
        frec[v[i]]++;                   // numaram aparitiile
    }

    for (int val = 0; val <= valMax; val++) {
        for (int k = 0; k < frec[val]; k++) {
            cout << val << " ";         // rescriem valoarea de frec[val] ori
        }
    }
    return 0;
}

Pentru {3, 1, 3, 2, 1} → 1 1 2 3 3.

Observația-cheie

Vectorul de frecvențe trebuie inițializat cu 0 (frec[1001] = {0}). Altfel pornește de la gunoi și numărătoarea e complet greșită. E o aplicație directă a vectorilor de frecvență.

Când o folosești (și când nu)

Da: valori întregi într-un interval mic și cunoscut (note 1–10, vârste, litere). Atunci e O(n + V), mai rapidă decât orice sortare prin comparație.
Nu: valori uriașe (până la un miliard) → ai avea nevoie de un vector de frecvențe de un miliard de poziții, imposibil de alocat. Acolo folosești std::sort.

Complexitate

Metodă	Timp	Spațiu
sortare prin numărare	O(n + V)	O(V)
sortare prin comparație	O(n log n)	O(1)–O(n)

unde V = valoarea maximă. Câștigi când V e mic; pierzi (la memorie) când V e enorm.

Greșeli frecvente

Capcane reale la sortarea prin numărare:

Vector de frecvențe neinițializat: fără = {0}, aduni peste gunoi → rezultat aberant.
Valori prea mari: frec indexat după valoare cere O(V) memorie. Pentru valori până la 10⁹ nu încape — folosește altă sortare.
Valori negative: indicii unui vector pornesc de la 0; valorile negative ies din interval. Deplasează cu un offset (frec[v[i] + OFFSET]).
Depășești dimensiunea lui frec: aloci frec[1001] dar valorile ajung la 5000 → scrii în afara vectorului. Dimensionează după valoarea maximă posibilă.

De reținut

Sortare fără comparații: numeri aparițiile în frec[], apoi rescrii valorile crescător.
Eficientă O(n + V) doar pentru valori întregi într-un interval mic (inițializează frec cu 0).
Pentru valori uriașe sau negative fără offset, folosește std::sort.