- Se numără
- Tocmai mutată
- La locul lor
Sortarea prin numărare
Sortarea prin numărare funcționează când valorile sunt numere întregi dintr-un interval mic. Ține câte un contor pentru fiecare valoare posibilă, numără de câte ori apare fiecare și din aceste numărători știe exact unde trebuie pusă fiecare valoare. Urmăriți cum se umplu contoarele în timp ce lista este citită, apoi cum se golesc pe măsură ce fiecare valoare se mută în blocul ei, câte o mutare. Apăsați Redare pentru a urmări sortarea sau Pas și Înapoi pentru a avansa câte o mutare. Trageți glisorul pentru pași ca să săriți oriunde. Banda dintre listă și rândul de buffer are câte un contor pentru fiecare valoare. Casetele numără valorile numărate, mutările și contoarele. Alegeți câte bare sunt, cum încep sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Alegeți câte bare sunt și cum încep sau introduceți propriile numere întregi. Încercați o listă cu puține valori distincte.
- Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte o valoare. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
- Urmăriți contoarele: se umplu în timp ce lista este citită, apoi scad pe măsură ce fiecare valoare este plasată.
Cum funcționează sortarea prin numărare
Creați un contor pentru fiecare valoare, de la cea mai mică la cea mai mare. Citiți lista o dată și adunați unu la contorul fiecărei valori întâlnite. Apoi adunați numărătorile pornind de la cea mai mică valoare: blocul unei valori începe imediat după toate valorile mai mici. În final, parcurgeți din nou lista, mutați fiecare valoare pe următorul loc liber din blocul ei și copiați rezultatul înapoi.
Rapidă pentru un interval mic
Sortarea prin numărare citește lista de două ori și parcurge contoarele o dată, așa că efortul crește cu n + k: numărul de valori plus numărul de contoare. Pentru multe valori dintr-un interval mic, cum ar fi punctajele la examen de la 0 la 100 sau vârstele, întrece orice sortare prin comparare. Pentru un interval larg irosește timp și memorie pe contoare pe care nu le folosește nimeni: trei valori răspândite de la 1 la 1.000.000 ar avea nevoie de un milion de contoare. Este și pasul pe care sortarea radix îl repetă pentru fiecare cifră.
Întrebări frecvente
Cum funcționează sortarea prin numărare?
Numără de câte ori apare fiecare valoare, adună numărătorile ca să afle unde începe blocul fiecărei valori, apoi mută fiecare valoare direct pe următorul loc liber din blocul ei. Nu compară niciodată două valori.
Când merită folosită sortarea prin numărare?
Când valorile sunt numere întregi sau pot fi transformate în numere întregi, iar intervalul de la cea mai mică la cea mai mare nu este mult mai mare decât numărul de valori: note, vârste, coduri scurte. Atunci durează un timp proporțional cu n + k.
Este sortarea prin numărare stabilă?
Da, când valorile sunt mutate în ordinea din listă pe următorul loc liber din blocul lor, ca aici. De aceea sortarea radix o poate folosi pentru fiecare cifră.
De ce să nu scriem pur și simplu fiecare valoare de atâtea ori de câte ori a fost numărată?
Pentru numere simple funcționează și e chiar mai simplu. Dar datele reale conțin de obicei mai mult decât cheia, de exemplu un nume lângă fiecare punctaj, iar dacă scriem doar cheile numărate, acesta se pierde. Mutarea elementelor înseși păstrează tot ce e atașat.
Numerele mele sunt trimise undeva?
Nu. Sortarea rulează în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor