Sortarea prin numărare
Sortarea prin numărare nu sortează deloc comparând valori. Dacă știți că fiecare valoare este un număr întreg între, să zicem, 1 și 40, puteți pur și simplu să numărați câte sunt din fiecare și, din aceste numărători, să aflați unde trebuie pusă fiecare. Pentru un interval mic, asta e cam cea mai rapidă sortare posibilă.
Numărare
Găsiți cea mai mică și cea mai mare valoare și creați câte un contor pentru fiecare valoare dintre ele, toate pornind de la zero. Citiți lista o dată, de la început la sfârșit, și adunați unu la contorul fiecărei valori întâlnite. Contoarele formează acum o histogramă: câte valori de 1, câte de 2 și așa mai departe. Cu n valori și k contoare, asta durează n pași.
Adunare
Valorile egale cu cea mai mică valoare vin primele, așa că blocul lor începe pe locul 1. Blocul valorii următoare începe imediat după ele și așa mai departe: fiecare bloc începe după suma tuturor numărătorilor dinaintea lui. Aceste totaluri parțiale, numite sume prefix, transformă histograma într-o hartă a listei sortate. Asta durează k pași.
Plasare
Citiți lista a doua oară și mutați fiecare valoare pe următorul loc liber din blocul ei. Pentru că valorile sunt mutate în ordinea în care apar, valorile egale își păstrează ordinea inițială: sortarea prin numărare este stabilă. Copiați bufferul înapoi și lista este sortată. Aplicația arată cum fiecare contor scade din nou pe măsură ce valorile lui sunt plasate.
Un exemplu
Luați 4, 1, 3, 4, 2, 1, 4. Contoarele pentru valorile de la 1 la 4 ajung la 2, 1, 1 și 3. Adunarea dă blocurile: valorile 1 pe locurile 1 și 2, valoarea 2 pe locul 3, valoarea 3 pe locul 4 și valorile 4 pe locurile de la 5 la 7. Plasarea valorilor în ordinea din listă dă 1, 1, 2, 3, 4, 4, 4: 7 valori numărate, 14 mutări, 4 contoare și nicio comparație.
Când se folosește
Efortul total crește cu n + k. Când k este mic față de n, de exemplu o mie de punctaje la examen de la 0 la 100, sortarea prin numărare este mai rapidă decât orice sortare prin comparare, care are nevoie de aproximativ n log₂ n comparații. Când intervalul e larg, este risipitoare: câteva valori răspândite până la un milion au nevoie de un milion de contoare. Sortarea radix rezolvă asta rulând sortarea prin numărare o dată pentru fiecare cifră, așa că fiecare trecere are nevoie doar de zece contoare. Harold Seward a descris sortarea prin numărare, împreună cu sortarea radix, în 1954.
Explorați
Deschideți aplicația și apăsați Pas. Banda dintre listă și rândul de buffer arată câte un contor pentru fiecare valoare. Urmăriți cum se umplu contoarele în timp ce lista este citită, cum apar blocurile în buffer când se adună numărătorile și cum scad contoarele din nou pe măsură ce valorile sunt plasate. Alegeți puține valori distincte ca să vedeți blocuri mari sau introduceți numere îndepărtate ca să vedeți de câte contoare are nevoie un interval larg.
Întrebări frecvente
Care este complexitatea în timp a sortării prin numărare?
O(n + k) pentru n valori și k valori posibile, plus O(n + k) memorie suplimentară pentru contoare și buffer.
De ce sortarea prin numărare nu este mereu cea mai rapidă?
Pentru că costul ei depinde de intervalul valorilor, nu doar de câte sunt. Dacă intervalul e mult mai mare decât lista, majoritatea contoarelor rămân la zero, iar timpul și memoria se irosesc.
Poate sortarea prin numărare să lucreze cu numere negative?
Da. Contoarele merg de la cea mai mică valoare la cea mai mare, așa că scădeți cea mai mică valoare ca să obțineți indicele unui contor. Aplicația face la fel.
Este sortarea prin numărare stabilă?
Da, atâta timp cât valorile sunt mutate în ordinea din listă pe următorul loc liber din blocul lor. Sortarea radix depinde de asta.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați sortarea prin numărare