Sortarea radix prin interschimbare





Sortarea radix prin interschimbare

Se presupune ca se doreste sortarea elementelor tabloului a astfel incat toate elementele ale caror chei incep cu un bit zero sa fie tre cute in fata celor care incep cu 1.

o      Aceasta va avea drept consecinta formarea a doua partitii ale tabloului initial,



o      Aceste partitii la randul lor se sorteaza independent, conform aceleasi metode dupa cel de-al doilea bit al cheilor elementelor,

o      Cele 4 partitii rezultate dupa al 3-lea bit si asa mai departe.

Acest mod de lucru sugereaza abordarea recursiva a implementarii metodei de sortare.  Procesul se desfasoara exact ca si la partitionare:

o      Se baleaza tabloul de la stanga spre dreapta pana se gaseste un element a carui cheie care incepe cu 1;

o      Se baleeaza tabloul de la dreapta spre stanga pana se gaseste un element a carui cheie incepe cu 0;

o      Se interschimba cele doua elemente;

o      Procesul continua pana cand pointerii de parcurgere se intalnesc formand doua partitii.



o      O problema serioasa care afecteaza aceasta metoda se refera la degenerarea partitiilor.

o      Degenerarea partitiilor apare de obicei in situatia in care cheile sunt reprezentate prin numere mici (care incep cu multe zerouri).

o      Aceasta situatie apare frecvent in cazul caracterelor interpretate pe 8 biti.

o      Din punctul de vedere al performantei, metoda de sortare radix prin interschimbare sorteaza n chei de b biti utilizand un numar de comparatii de biti egal cu  n  b 

Cu alte cuvinte, sortarea radix prin interschimbare este liniara cu numarul de biti ai unei chei.









Copyright © Contact | Trimite referat