Comparatie intre diferite tipuri de sortari avansate. - Radix Sort.
Breviar teoretic
BrickSort
BucketSort
CountSort
RadixSort
Bibliografie
Concluzii
Contactati-ma !
Radix Sort este un algoritm ce nu foloseste comparatii de chei, ci distribuie cheile in grupe pe baza unei informatii particulare referitoare la natura cheilor. Fie tipul cheilor Key alcatuit din k componente: f1, f2, ..., fk cu tipurile t1, t2, ... tk. Se considera ca o cheie (a1, a2, ..., an) este inferioara unei chei (b1, b2, ..., bn) unde ai si bi sunt valori ale campului fi cu i=1, 2, ..., k daca exista o valoare j intre 0 si k-1 astfel incat: a1=b1, a2=b2, ..., aj=bj si aj+1<bj+1. RadixSort sorteaza dupa compartimente (grupe) mai intai dupa campul fk (considerat campul cel mai putin semnificativ), apoi dupa campul fk-1, si asa mai departe pana la campul f1 (considerat campul cel mai semnificativ).
Pentru a fi mai explicit vom considera un exemplu edificator: presupunem sortarea unor numere: 9999, 12345 si 32, sortare crescatoare. Mai intai aducem numerele la acelasi format (pe 5 digiti): 09999, 12345 si 00032. Deci campurile sunt: campul cel mai putin semnificativ este digitul cel mai putin semnificativ, iar campul cel mai semnificativ este digitul cel mai semnificativ. Asa cum am precizat, mai intai sortam informatia dupa campul cel mai putin semnificativ: 9>2>5, deci ordinea este: 00032, 12345, 09999. Apoi dupa campul de rang urmator (mentinand ordinea locala): 9>4>3. Deci se obtine: 00032, 12345, 09999. Apoi: 9>3>0, deci 00032, 12345, 09999. Apoi 9>2>0, deci tot 00032, 12345, 09999. Apoi ultimul pas: 1>0>0, deci 00032, 09999, 12345. Si am obtinut numerele sortate.
Se cuvine o observatie: pentru a mentine ordinea locala este necesar sa putem memora grupele de campuri in niste structuri auxiliaresi anume cozi). Deci sortarea nu mai este in situ (lat. pe loc). Pentru aceste cozi presupunem ca avem definiti operatorii:
NewQ() - creaza o noua coada (vida);
InsertQ(Q,e) - insereaza in coada Q elementul e;
DelQ(Q) - sterge elementul aflat in varful cozii Q;
TopQ(Q) - intoarce elementul aflat in varful cozii Q;
ConcatQ(Q1,Q2) - concateneaza cozile Q1 si Q2;
VidaQ(Q) - intoarce true daca coada Q este vida si false altfel.
Ipoteza de lucru: pentru a simplifica implementarea algoritmului vom presupune ca RadixSort va sorta numai numere intregi si pozitive. In acest caz, cel mai putin semnificativ camp este cel mai putin semnificativ bit de reprezentare binara, iar cel mai semnificativ camp este cel mai semnificativ bit de reprezentare binara. Fie de asemenea numarul de valori distincte ale componentelor cheilor: 2, adica {0,1} si k=16 (reprezentare pe doi octeti). Numerele sunt retinute intr-un vector A. Algoritmul in pseudocod este:
RadixSort(A)
{pentru(i<-k;i>=1;i<-i-1) executa:
{cat timp(v in ti) executa: Bi[v]=vid;
cat timp e in A executa: Bi=InsertQ(Bi[v],e);
}
cat timp(v in ti executa: A=ConcatQ(A,Bi[v]);
}
Gata !
Codul algoritmului RadixSort in C++ parametrizat se afla aici
Codul algoritmului RadixSort in J++ se afla aici
Corectitudinea algoritmului reiese din pseudocodul algoritmului: algoritmul va realiza intr-o prima etapa o distributie pe grupe a tuturor elementelor in functie de cel mai putin semnificativ camp. Apoi aceste grupe se concateneaza in ordine. Atentie: in ordine ! Apoi se repeta ceea ce am descris mai sus insa fata de campul cu pondere imediat urmatoare. Tot asa mai departe pana cand se va realiza gruparea si apoi concatenarea fata de cel mai semnificativ rang. Rezulta ca in urma concatenarii ultime, vectorul initial este sortat.
Complexitatea algoritmului depinde de implementarea cozii ca structura de date. Cu cat scade complexitatea cozii, cu atat va scadea si complexitatea algoritmului RadixSort. Algoritmul considera reprezentarea elementelor sub forma unei liste si nu a unui vector, deci orice vector va fi transformat intr-o lista inlantuita, operatie ce are costul O(n). Avantajul folosirii listelor fata de vectorii clasici este redat de faptul ca la operatia de concatenare nu mai trebuie copiata informatia dintr-un vector in altul, ci se schimba pur si simplu pointerii listei. Daca notam cu si numarul de valori distincte ale tipului ti, atunci primul ciclu (ne referim la ciclurile din pseudocod) are complexitatea teta(si), al doilea ciclu are complexitatea teta(n), iar ultimul ciclu are complexitatea teta(si). Rezulta complexitatea totala a algoritmului data de relatia:
. In conditiile in care am presupus ca si=2 si k=16, formula devine:
.
Deci complexitatea intregului algoritm in ipoteza de lucru este: O(n).
Pentru a rula pagina la inceput (la meniu) dati un click aici.