Sortarea radix

Sortarea radix e excepția printre algoritmii de sortare: nu întreabă niciodată care dintre două valori e mai mare. Citește numerele cifră cu cifră și le sortează după câte o cifră, folosind zece găleți. Ideea e mai veche decât calculatoarele: așa funcționau mașinile de sortat cartele perforate.

Barele unei liste deasupra unui rând de zece găleți etichetate de la 0 la 9, cu o valoare care cade în găleata ultimei sale cifre
Barele unei liste deasupra unui rând de zece găleți etichetate de la 0 la 9, cu o valoare care cade în găleata ultimei sale cifre

Ideea

Sortați numerele doar după cifra unităților. Apoi sortați-le după cifra zecilor, dar astfel încât numerele cu aceeași cifră a zecilor să rămână în ordinea dată de prima trecere. Apoi după sute, la fel. După ultima trecere lista e sortată: sutele decid primele, numerele cu aceleași sute sunt deja ordonate după zeci, iar cele cu aceleași zeci, după unități.

O trecere, cu găleți

Fiecare trecere folosește zece găleți, câte una pentru fiecare cifră de la 0 la 9. Parcurgeți lista de la început la sfârșit și mutați fiecare număr în găleata cifrei sale, în spatele numerelor aflate deja acolo. Apoi goliți gălețile înapoi în listă, în ordine, începând cu găleata 0. Faptul că numerele sunt mutate în ordinea din listă și adăugate la coada găleții face ca trecerea să fie stabilă. Aplicația numără mai întâi numerele pentru fiecare cifră, ca gălețile să poată sta una lângă alta pe un singur rând, fiecare începând imediat după cea dinainte: aceasta este o sortare prin numărare pe o cifră.

Un exemplu

Luați 170, 45, 75, 90, 802, 24, 2, 66. După cifra unităților: 170, 90, 802, 2, 24, 45, 75, 66. După cifra zecilor: 802, 2, 24, 45, 66, 170, 75, 90; observați că 802 și 2, ambele cu cifra zecilor 0, își păstrează ordinea din prima trecere. După cifra sutelor: 2, 24, 45, 66, 75, 90, 170, 802. Trei treceri peste opt numere: 24 de cifre citite și 48 de mutări, și nicio comparație.

Cât de rapidă este?

Fiecare trecere citește o cifră din fiecare număr și mută fiecare număr de două ori, deci pentru n numere cu d cifre munca crește cu n · d. O sortare prin comparare are nevoie în cel mai rău caz de cel puțin aproximativ n log₂ n comparații, pentru că trebuie să deosebească n! ordini posibile, câte o întrebare cu da sau nu. Sortarea radix nu e legată de această limită, fiindcă nu pune niciodată astfel de întrebări. Pentru multe chei scurte, cum ar fi un milion de numere sub 1.000, trei treceri înseamnă mult mai puțină muncă decât cele circa 20 de milioane de comparații de care ar avea nevoie o sortare prin comparare. Pentru chei lungi sau puține valori, avantajul dispare.

LSD și MSD, plus istorie

Versiunea prezentată aici începe cu cifra cea mai puțin semnificativă (LSD). Invers, cu cifra cea mai semnificativă întâi (MSD), lista se împarte în găleți după prima cifră și fiecare găleată se sortează separat, ceea ce se potrivește pentru șiruri de lungimi diferite. Sortarea radix vine de la sortatoarele de cartele perforate apărute după mașinile de tabulat ale lui Herman Hollerith de la recensământul SUA din 1890: un sortator lăsa fiecare cartelă să cadă într-unul din zece buzunare după gaura dintr-o coloană, iar operatorii treceau teancul prin mașină o dată pentru fiecare coloană, începând cu ultima.

O mașină de tabulatură Hollerith cu cartele perforate la Computer History Museum, de tipul folosit la recensământul SUA din 1890. Operatorii treceau un pachet printr-un sortator o dată pe coloană, strămoșul sortării radix.
O mașină de tabulatură Hollerith cu cartele perforate la Computer History Museum, de tipul folosit la recensământul SUA din 1890. Operatorii treceau un pachet printr-un sortator o dată pe coloană, strămoșul sortării radix.

Explorați

Deschideți aplicația și apăsați Pas. Fiecare trecere numără mai întâi cifrele, ceea ce delimitează gălețile de la 0 la 9 pe rândul de sub listă. Apoi numerele cad unul câte unul în gălețile lor, cu găleata activă evidențiată, și sunt copiate înapoi. Introduceți propriile numere până la 999, de pildă cele din exemplul de mai sus, ca să vedeți toate cele trei treceri.

Întrebări frecvente

Care este complexitatea în timp a sortării radix?

O(n · d) pentru n chei de d cifre într-o bază fixă, plus costul găleților la fiecare trecere. Are nevoie de O(n) memorie suplimentară pentru bufferul în care stau gălețile.

Este sortarea radix stabilă?

Sortarea radix LSD trebuie să fie: funcționează doar pentru că fiecare trecere păstrează valorile cu aceeași cifră în ordinea în care au venit. Prin urmare, și rezultatul final e stabil.

Poate sortarea radix să lucreze cu numere negative sau zecimale?

Nu direct, dar se poate cu un truc: deplasați numerele negative ca să devină toate pozitive sau sortați-le separat și inversați-le. Numerele în virgulă mobilă pot fi sortate după reprezentarea lor pe biți, după o mică transformare.

De ce baza 10?

Pentru că e ușor de urmărit. Calculatoarele sortează de obicei după 8 sau 16 biți odată, așa că un număr pe 32 de biți necesită patru sau două treceri, cu 256 sau 65.536 de găleți.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați sortarea radix