Sortare prin numărare

De ce contează?

Ai 1.000 de bilete de loterie, fiecare cu un număr de la 1 la 100. Vrei să le sortezi. Soluția deșteaptă: faci 100 de grămezi (câte una per număr), numeri câte bilete sunt în fiecare grămadă, apoi le pui la loc în ordine crescătoare. Fără nicio comparație directă între bilete.

Ideea cheie

Sortarea prin numărare nu compară elemente — numără câte valori sunt de fiecare fel, apoi reconstruiește vectorul sortat din contoare.

Exemplu: pentru 4 2 2 8 3 3 1:

frec[1]=1, frec[2]=2, frec[3]=2, frec[4]=1, frec[8]=1
Rezultat: 1 2 2 3 3 4 8

Observă: nici o comparație între elemente — doar numărare și reconstituire.

Algoritmul

Pas 1: construim frec[]
       frec[v[i]]++ pentru fiecare i din 0..n-1

Pas 2: reconstruim vectorul sortat
       pentru val de la 0 la maxVal:
           punem frec[val] copii ale lui val inapoi in vector

Implementare C++

#include <iostream>
using namespace std;

int frec[1001];   // global = 0

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        frec[x]++;          // numaram fiecare valoare
    }

    // reconstruim vectorul sortat
    for (int val = 0; val <= 1000; val++) {
        for (int k = 0; k < frec[val]; k++) {
            cout << val << " ";
        }
    }
    return 0;
}

Exemplu: Input 7 / 4 2 2 8 3 3 1 → 1 2 2 3 3 4 8

Dacă trebuie să păstrăm vectorul

int v[50001], poz = 0;
for (int i = 0; i < n; i++) { cin >> v[i]; frec[v[i]]++; }

for (int val = 0; val <= 1000; val++) {
    for (int k = 0; k < frec[val]; k++) {
        v[poz++] = val;
    }
}
// v este acum sortat

Complexitate

Pas	Timp
Construire frec[]	O(n)
Reconstruire vector	O(maxVal)
Total	O(n + maxVal)

Spațiu: O(maxVal) pentru frec[].

Observația-cheie

Limitele sortării prin numărare: valorile trebuie să fie întregi într-un interval cunoscut și nu prea mare. Nu funcționează pentru numere reale, string-uri sau valori cu interval uriaș (ex. până la 10⁹) — acolo frec[] nu încape în memorie.

Vizualizare

Indiciu

Vizualizatorul arată cele două etape: construcția vectorului de frecvență (faza de numărare) și reconstrucția vectorului sortat (faza de scriere în ordine).

Greșeli frecvente

Greșeala 1: frec[] prea mic — dacă valorile merg până la 1000 și ai int frec[100], accesezi memorie invalidă la frec[500]. Dimensiunea trebuie să acopere toate valorile posibile.

Greșeala 2: Bucla de reconstruire merge până la val <= n (numărul de elemente) în loc de val <= maxVal (valoarea maximă). Confunzi numărul de elemente cu intervalul valorilor.

Greșeala 3: Uiți să resetezi frec[] între teste multiple. Declarat global e 0 la start; dacă rulezi mai mulți pași, resetează manual cu un for.

Recapitulare

Numărarea: frec[v[i]]++ pentru fiecare element; reconstruire în ordine din contoare.
Complexitate O(n + maxVal) — mai rapid decât O(n log n) când maxVal e mic.
Limitare: valori întregi, interval cunoscut și rezonabil (sub ~10⁶).