Sortarea bazata pe baze de numeratie. Radix sort

Sortarea bazata pe baze de numeratie. Radix sort

Metodele de sortare care iau in considerare proprietatile digitale ale numerelor sunt metodele de sortare bazate pe baze de numeratie ('radix sort'). 

Algoritmii de tip baza de numeratie, trateaza cheile ca si numere reprezentate intr-o baza de numeratie m, unde m poate lua diferite valori ('radix') si proceseaza cifrele individuale ale numarului.

Un exemplu sugestiv il reprezinta sortarea unui teanc de cartele care au perforate pe ele numere formate trei cifre.

o      Se grupeaza cartelele in 10 grupe distincte, prima cuprinzand cheile mai mici decat 100, a doua cheile cuprinse intre 100 si 199, etc., adica se realizeaza o sortare dupa cifra sutelor.

o      In continuare se sorteaza pe rand grupele formate aplicand aceeasi metoda, dupa cifra zecilor,

o      Apoi fiecare grupa nou formata, dupa cifra unitatilor.

o      Acesta este un exemplu simplu de sortare radix cu m = 10.

o      Pentru sistemele de calcul, unde prelucrarile se fac exclusiv in baza 2, se preteaza cel mai bine metodele de sortare radix care opereaza cu numere binare.

o      Exista doua metode de baza pentru implementarea sortarii radix.

Prima metoda examineaza bitii cheilor de la stanga la dreapta si se numeste sortare radix prin interschimbare ('radix exchange sort').

o      Ea se bazeaza pe faptul ca rezultatul comparatiei a doua chei este determinat de valoarea bitilor din prima pozitie la care ele difera.

o      Astfel, elementele ale caror chei au primul bit 0 sunt trecute in fata celor care au primul bit 1;

o      In continuare in fiecare grup astfel format se aplica aceeasi metoda pentru bitul urmator si asa mai departe.

o      Sortarea propriu-zisa se realizeaza prin schimbarea sistematica a elementelor in maniera precizata.

A doua metoda se numeste sortare radix directa ('straight radix sort').

o      Ea examineaza bitii din cadrul cheilor de la dreapta la stanga si se bazeaza pe principiul interesant care reduce sortarea cheilor de b-biti la b sortari ale unor chei de 1bit.