- Găleata curentă
- Tocmai mutată
- Copiate înapoi
- La locul lor
Sortarea radix
Sortarea radix ordonează numere întregi fără să compare vreodată două dintre ele. Sortează lista după cifra unităților, apoi după cifra zecilor, apoi după a sutelor, de fiecare dată mutând valorile în zece găleți și copiindu-le înapoi în ordine. Urmăriți cum se umplu gălețile pe rândul de sub listă, câte o mutare, și cum lista devine sortată după tot mai multe cifre. 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. Gălețile de la 0 la 9 stau una lângă alta pe rândul de sub listă. Casetele numără cifrele citite, mutările și trecerile. Alegeți câte bare sunt, cum încep sau introduceți propriile numere, până la 999. 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, până la 999, ca să vedeți și trecerea pentru sute.
- Apăsați Redare sau folosiți Pas și Înapoi ca să mutați câte o valoare. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
- Urmăriți fiecare trecere: se numără cifrele, fiecare valoare e mutată în găleata ei, apoi gălețile sunt copiate înapoi.
Cum funcționează sortarea radix
Priviți doar ultima cifră a fiecărui număr și sortați lista după ea: puneți fiecare număr într-una din zece găleți, de la 0 la 9, în ordinea în care vin, apoi copiați gălețile înapoi, una după alta. Faceți la fel cu cifra zecilor, apoi cu a sutelor. Pentru că fiecare trecere păstrează ordinea numerelor care au aceeași cifră, trecerile anterioare decid în continuare ordinea dintre ele, iar după ultima trecere toată lista e sortată.
Nicio comparație
Sortările prin comparare au nevoie în cel mai rău caz de cel puțin aproximativ n log₂ n comparații, oricât de ingenios ar fi trucul folosit. Sortarea radix ocolește această limită citind cifre: fiecare trecere citește o cifră din fiecare valoare și mută fiecare valoare de două ori, deci d cifre înseamnă d treceri, iar munca crește cu n · d. Pentru liste lungi cu chei scurte merită: un milion de numere până la 999 necesită trei treceri, pe când o sortare prin comparare are nevoie de circa 20 de milioane de comparații. Prețul este că funcționează doar pentru chei formate din cifre sau caractere și are nevoie de spațiu pentru găleți.
Întrebări frecvente
Cum funcționează sortarea radix?
Sortează numerele după ultima cifră, apoi după cifra dinaintea ei și tot așa până la prima cifră. Fiecare trecere pune numerele în zece găleți după acea cifră, păstrându-le ordinea, și copiază gălețile înapoi. După trecerea pentru cifra cea mai semnificativă, lista e sortată.
De ce se începe cu ultima cifră?
Pentru că fiecare trecere e stabilă: numerele cu aceeași cifră păstrează ordinea primită în trecerile anterioare. Așa că ultima trecere, pe prima cifră, decide ordinea, iar egalitățile sunt departajate de cifrele deja sortate. Aceasta se numește sortare radix LSD (least significant digit, cifra cea mai puțin semnificativă).
Este sortarea radix mai rapidă decât quicksort?
Poate fi, pentru multe chei scurte: munca ei crește cu numărul de valori înmulțit cu numărul de cifre, fără n log n. Pentru puține valori, chei foarte lungi sau date care nu sunt formate din cifre, quicksort și sortarea prin interclasare sunt de obicei mai rapide și mai simple.
Ce legătură are cu sortarea prin numărare?
Fiecare trecere a sortării radix este o sortare prin numărare pe o cifră: se numără câte valori are fiecare cifră, se calculează unde începe fiecare găleată și valorile sunt mutate acolo, în ordine.
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