Sortare Radix

Sortare Radix
Exemplu de funcționare a algoritmului.
Clasă	Algoritm de sortare
Structură de date	Matrice
Cel mai rău caz din punct de vedere temporal	$O(kN)$ ${\ displaystyle O (kN)}$ ${\ displaystyle O (kN)}$
Cel mai rău caz spațial	$O(kN)$ ${\ displaystyle O (kN)}$ ${\ displaystyle O (kN)}$
Optim	Depinde de date
Manual

Sortarea Radix este un algoritm de sortare pentru valori numerice întregi cu complexitate de calcul O ( $n k$ ${\ displaystyle nk}$ $nk$ ), unde este $n$ ${\ displaystyle n}$ $n$ este lungimea matricei și $k$ ${\ displaystyle k}$ $k$ este media numărului de cifre al $n$ ${\ displaystyle n}$ $n$ numere.

Sortarea Radix utilizează o procedură contraintuitivă pentru oameni, dar mai ușor de implementat. Sortează după poziția cifrei, dar începând de la cea mai puțin semnificativă cifră. Aceasta este astfel încât algoritmul să nu funcționeze recursiv pe subprobleme de dimensiune care nu pot fi evaluate a priori.

Considerații de algoritm

Algoritmul de sortare Radix are o complexitate de calcul variabilă bazată pe valoarea k. Dacă k este mai mic decât n, nu există câștig în ceea ce privește sortarea de numărare care funcționează în timp liniar.

Dacă k este mai mare decât n, algoritmul poate fi mai rău chiar decât algoritmii de clasificare mai clasici pentru comparație de timp aproape liniară, cum ar fi Quicksort sau Mergesort .

Folosind o valoare ca bază a algoritmului $B=\Theta (n)$ ${\ displaystyle B = \ Theta (n)}$ ${\ displaystyle B = \ Theta (n)}$ timpul de sortare devine ${\mathcal {O}}\left(n\left(1+{\log(k) \over \log(n)}\right)\right)$ ${\ displaystyle {\ mathcal {O}} \ left (n \ left (1 + {\ log (k) \ over \ log (n)} \ right) \ right)}$ ${\ displaystyle {\ mathcal {O}} \ left (n \ left (1 + {\ log (k) \ over \ log (n)} \ right) \ right)}$

Definiția anterioară este demonstrabilă prin amintirea faptului că există $\log _{n}(k)={\mathcal {O}}(\log _{n}(k))$ ${\ displaystyle \ log _ {n} (k) = {\ mathcal {O}} (\ log _ {n} (k))}$ ${\ displaystyle \ log _ {n} (k) = {\ mathcal {O}} (\ log _ {n} (k))}$ trece de tip întreg și fiecare ia timp ${\mathcal {O}}(n)$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ .

Folosind regulile pentru schimbarea bazei logaritmilor , timpul total este dat de ${\mathcal {O}}(n\log _{n}(k))={\mathcal {O}}\left(n{\log(k) \over \log(n)}\right)$ ${\ displaystyle {\ mathcal {O}} (n \ log _ {n} (k)) = {\ mathcal {O}} \ left (n {\ log (k) \ over \ log (n)} \ right )}}$ ${\ displaystyle {\ mathcal {O}} (n \ log _ {n} (k)) = {\ mathcal {O}} \ left (n {\ log (k) \ over \ log (n)} \ right )}}$ .

La această cantitate trebuie adăugată ${\mathcal {O}}(n)$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ să contemplăm cazul în care k <n, întrucât secvența trebuie cel puțin citită.

Pseudo cod

 RADIX-SORT (A, d)
   pentru i <- 1 la d
       do folosește o sortare stabilă pentru a sorta matricea A pe cifra i

fundal

Radix Sort este algoritmul folosit de mașini pentru sortarea cărților perforate , care se găsesc acum doar în muzeele de calculatoare.

Alte proiecte

Wikibooks conține implementări de sortare radix
Wikimedia Commons conține imagini sau alte fișiere despre sortarea radix

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stivă · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel