Sortarea radix directa
O alta varianta de
implementare a sortarii radix este aceea de a examina bitii cheilor
elementelor de la dreapta la stanga.
Este metoda utilizata de
vechile masini de sortat cartele.
o
Teancul de cartele trece de 80 de ori prin
masina, cate odata pentru fiecare coloana incepand de la
dreapta spre stanga, fiecare trecere realizand sortarea dupa o
coloana.
o
In cazul cheilor, cand se ajunge la bitul i venind dinspre dreapta, cheile sunt
gata sortate pe ultimii i-1 biti
ai lor.
o
Sortarea continua extragand toate elementele
ale caror chei au zero pe pozitia i
si plasandu-le in fata celor care au 1 pe aceeasi pozitie.
Nu este usor de demonstrat ca metoda este
corecta: de fapt ea este corecta
numai in situatia in care sortarea dupa 1 bit este stabila.
Datorita
acestei cerinte,
sortarea radix prin interschimbare nu
poate fi utilizata deoarece nu este o metoda de sortare stabila.
- In ultima instanta
trebuie sortat stabil un tablou cu numai doua valori 0 si 1.
- Metoda
bazata pe determinarea distributiilor (distribution counting) poate fi utilizata cu succes in acest
scop.
- Se considera algoritmul
de sortare bazat pe determinarea distributiei cheilor in care:
- Se ia m = 2 si
- Se inlocuieste a[i].cheie
cu biti(a[i].cheie,k,1) pentru k = 0, 1, 2, , b -1 (adica
se extrage din cheie 1 bit situat la distanta k fata de
sfarsitul cheii) .
- Se
obtine astfel, o metoda de sortare stabila a tabloului a,
dupa bitul k, de la
dreapta la stanga, rezultatul fiind memorat intr-o tablou temporar t .
- Se reia sortarea bazata
pe determinarea distributiilor pentru fiecare bit al cheii respectiv
pentru pentru k = 0, 1, 2, , b -1
- Rezulta ca pentru
sortare sunt necesare b treceri unde b este lungimea cheii.
- De fapt, nu este indicat sa se lucreze cu m = 2 , ci
este convenabil ca m sa fie
cat mai mare.
- Daca se prelucreaza
m biti odata, timpul de sortare scade, dar tabela de
distributii creste ca
dimensiune ea trebuind sa contina m1 = 2m
locatii.
- In acest mod, sortarea
radix-directa devine o generalizare
a sortarii bazate pe determinarea distributiilor.
- Algoritmul
din secventa [3.2.9.2.a] sorteaza dupa aceasta
metoda tabloul a[1..n],
- Cheile sunt de b biti lungime,
- Cheile sunt parcurse de la
dreapta la stanga, procesand cate m biti odata.
- Se
utilizeaza tabloul suplimentar t[1..n].
- Procedura
functioneaza numai
daca b este multiplu de m deoarece algoritmul de sortare divizeaza bitii
cheilor intr-un numar intreg de parti de dimensiuni egale
care se proceseaza deodata.
- Daca
se ia m = b se
obtine sortarea bazata pe
determinarea distributiilor;
- Daca se ia m = 1
rezulta sortarea radix directa.
- Implementarea
propusa sorteaza tabloul a in tabloul t si dupa fiecare pas
de sortare recopiaza tabloul t in a (ultima bucla FOR).
