Sortarea prin numărare

Sortarea prin numărare este potrivită pentru valori întregi dintr-un interval mic cunoscut. Ținem un contor pentru fiecare valoare posibilă, apoi reconstruim șirul în ordine crescătoare. Pentru $[4;2;4]$, valoarea 2 apare o dată, iar 4 apare de două ori; rezultatul este $[2;4;4]$.

Sortarea prin numărare se folosește pentru numere întregi dintr-un interval mic și cunoscut $[L;R]$. Se pregătește un tablou de $R-L+1$ contoare inițializate cu 0, în care fr[x - L] păstrează de câte ori apare valoarea $x$. Prima parcurgere a șirului mărește contorul fiecărei valori citite. A doua parcurgere reconstruiește șirul în ordine crescătoare: pentru fiecare valoare, în ordinea $L,L+1,\dots ,R$, se scrie valoarea de atâtea ori cât spune contorul ei. Un contor 0 omite valoarea, iar un contor 3 produce trei copii consecutive. Metoda nu compară elementele între ele. Timpul este $O(n+R-L+1)$, iar memoria auxiliară este $O(R-L+1)$, deci este avantajoasă numai când intervalul este mic în comparație cu $n$ și nu este potrivită pentru valori foarte mari sau reale.

Exemplul 1 — valori între 0 și 3 (Python).

v = [2, 1, 2, 3]
frecventa = [0] * 4
for x in v:
    frecventa[x] += 1
rezultat = []
for valoare in range(4):
    rezultat.extend([valoare] * frecventa[valoare])
print(*rezultat)

Vectorul de frecvențe evoluează prin [0,0,1,0], [0,1,1,0], [0,1,2,0] și [0,1,2,1]. Reconstruirea scrie 1 o dată, 2 de două ori și 3 o dată; ieșirea este 1 2 2 3. Valoarea 0 are frecvența 0 și nu apare.

Exemplul 2 — varianta C++. Aceleași două parcurgeri, scrise în C++ pentru valori între 0 și 3:

#include <iostream>
using namespace std;
int main() {
    int v[] = {2, 1, 2, 3}, frecventa[4] = {};
    for (int i = 0; i < 4; ++i)
        ++frecventa[v[i]];
    for (int valoare = 0; valoare <= 3; ++valoare)
        for (int k = 0; k < frecventa[valoare]; ++k)
            cout << valoare << " ";
    return 0;
}

Programul afișează 1 2 2 3 , inclusiv spațiul de la sfârșit.

Exemplul 3 — interval cu valori negative. Pentru valori din $[-2;1]$ se folosesc patru contoare, iar valoarea $x$ se înregistrează la indicele $x-L=x+2$. Șirul $-2,1,-2,0,1$ produce contoarele [2,0,1,2]: indicele 0 corespunde lui $-2$ (apare de două ori), indicele 1 lui $-1$ (nu apare), indicele 2 lui 0 (o dată) și indicele 3 lui 1 (de două ori). Reconstruirea scrie $-2,-2,0,1,1$. Tot astfel, notele 7, 9, 7, 10, 5, 9, 7 dau frecvențele 5:1, 7:3, 9:2 și 10:1, deci șirul sortat este $5,7,7,7,9,9,10$.

Alegerea metodei depinde de raportul dintre $n$ și mărimea intervalului. Pentru un milion de note între 1 și 10 sunt suficiente 10 contoare, deci metoda este foarte rapidă și economică. Pentru 10 valori cuprinse între 1 și un milion ar fi nevoie de un milion de contoare, deci metoda nu este potrivită.

Reconstruirea simplă nu păstrează ordinea inițială a elementelor egale dacă ele au și alte câmpuri, pentru că scrie doar valoarea. Sortarea stabilă a unor înregistrări cere contoare cumulate și un vector rezultat în care elementele se plasează de la sfârșit.

Exemplul 4 — sortarea stabilă. Pentru șirul $2,1,2,0$ din intervalul $[0;2]$, frecvențele sunt [1,1,2], iar contoarele cumulate [1,2,4] arată, pentru fiecare valoare, ultima poziție ocupată de ea în șirul sortat (poziții de la 1). Elementele se parcurg de la sfârșit spre început: 0 merge pe poziția 1, al doilea 2 pe poziția 4, valoarea 1 pe poziția 2, iar primul 2 pe poziția 3, după fiecare plasare scăzând cu 1 contorul valorii. Rezultatul este $0,1,2,2$, iar cele două valori egale cu 2 rămân în ordinea inițială.

La reconstrucție, un contor 0 omite valoarea respectivă, iar un contor 3 produce trei copii consecutive. Pentru domeniul $[-2;1]$, indicele 0 corespunde lui $-2$, iar indicele 3 corespunde lui 1. Dacă valorile sunt din $[0;M]$, declară $M+1$ contoare, inclusiv cel pentru 0. La date cu câmpuri asociate, verifică dacă enunțul cere păstrarea ordinii elementelor egale. Nu confunda sortarea prin numărare cu numărarea elementelor mai mici: aceasta din urmă calculează, pentru fiecare element, poziția finală.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int v[] = {3, 0, 2, 3, 0, 0}, fr[4] = {0};
for (int i = 0; i < 6; i++)
    fr[v[i]]++;
for (int x = 0; x <= 3; x++)
    for (int k = 0; k < fr[x]; k++)
        cout << x << ' ';

• a) 0 0 0 2 3 3
• b) 0 2 3
• c) 3 3 2 0 0 0
• d) 0 0 0 1 2 3 3

Răspunsul corect este a). Frecvențele sunt: 0 apare de 3 ori, 1 nu apare, 2 apare o dată și 3 apare de două ori. Reconstruirea scrie valorile în ordinea crescătoare: 0 0 0, apoi nimic pentru 1, apoi 2, apoi 3 3. Varianta b) scrie fiecare valoare o singură dată, varianta c) este ordinea descrescătoare, iar varianta d) include valoarea 1, care are frecvența 0.

Al doilea exemplu. Un șir are $n=10^5$ elemente, cu valori întregi din intervalul $[1;1000]$. Câte contoare sunt necesare și câte operații face metoda? Sunt $1000-1+1=1000$ contoare. Prima parcurgere face $10^5$ incrementări, iar a doua trece prin cele 1000 de contoare și scrie în total $10^5$ valori. Numărul operațiilor este de ordinul $n+1000$, adică $O(n+R-L+1)$. Metoda este avantajoasă, pentru că intervalul este mult mai mic decât $n$.

Greșeli frecvente

• Greșit: sortarea prin numărare compară elementele între ele.
  Corect: numără aparițiile fiecărei valori și reconstruiește șirul.
• Greșit: este potrivită pentru orice valori întregi.
  Corect: este potrivită când intervalul valorilor este mic în comparație cu numărul de elemente.
• Greșit: valorile negative pot fi folosite direct ca indici.
  Corect: indicele este x - L, unde $L$ este limita inferioară a intervalului.

Înainte și după