Sortarea prin numărare (Counting Sort) în C++

Sortarea prin numărare (Counting Sort) în C++

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 vv de lungime nn indexat de la 11 și cu elementele cuprinse între 00 și MAX1\mathrm{MAX} - 1

Algoritm

Se parcurge vectorul vv și se rețin frecvențele elementelor sale în vectorul de frecvență frq\mathrm{frq} Apoi, se parcurge vectorul frq\mathrm{frq} de la 00 la MAX1\mathrm{MAX} - 1 dacă vrem să realizăm o sortare crescătoare, sau de la MAX1\mathrm{MAX} - 1 la 00 în caz contrar. Considerăm kk noua lungime a vectorului, și o inițializăm cu 00 Pentru fiecare element frq[i]\mathrm{frq}[i] adăugăm valoarea ii la finalul vectorului (pe poziția kk ce mai întâi este incrementată) de frq[i]\mathrm{frq}[i] ori, pentru că de atâtea ori apare aceasta în vv 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 vv vectorul sortat cu ww iar vectorul de frecvență cu frq\mathrm{frq}

Exemplu: Sortare prin numărare

Implementare în C++

Mai jos este implementarea algoritmului în C++. Nimic special… L-am parcurs pe vv de la 11 la nn și am actualizat frecvența (numărul de apariții) ale elementului curent (v[i]\htmlClass{katexified}{(} v[i] prin frq[v[i]]++. Apoi, l-am parcurs pe frq\mathrm{frq} de la 00 la MAX1\mathrm{MAX} - 1 (pentru că ăsta e intervalul de valori al elementelor lui vv Pentru fiecare element frq[i]\mathrm{frq}[i] cât timp e nenul, îl decrementez, incrementez noul capăt al lui vv (k\htmlClass{katexified}{(} k și îl copiez acolo pe ii

for (int i = 1; i <= n; i++)
frq[v[i]]++;
int k = 0;
for (int i = 0; i < MAX; i++)
while (frq[i]--)
v[++k] = 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 vv 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.

Sortarea prin numărare
#include <bits/stdc++.h>
using namespace std;
const int MAX = 618;
int n;
int frq[MAX];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
frq[x]++;
}
for (int i = 0; i < MAX; i++)
while (frq[i]--)
cout << i << ' ';
cout << '\n';
return 0;
}

Complexitate

Sortarea prin numărare face 2n+MAX2 \cdot n + \mathrm{MAX} pași. Un nn de la parcurgerea lui vv un MAX\mathrm{MAX} de la parcurgerea lui frq\mathrm{frq} și încă un nn de la reintroducerea elementelor în vv Asta înseamnă o complexitate liniară, de ordinul O(n+MAX)O(n + \mathrm{MAX}) Complexitatea spațiului auxiliar este O(MAX)O(\mathrm{MAX}) pentru că este necesar un vector de frecvență de lungime MAX\mathrm{MAX}

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(nlogn)O(n \log n) cum ar fi QuickSort, atunci când MAX<nlog2n\mathrm{MAX} \lt n \log_2 n Similar, sortarea prin numărare e mai bună decât un algoritm în O(n2)O(n^2) ca sortarea prin selecție, când MAX<n2\mathrm{MAX} \lt n^2

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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii