Introduzione
Radix sort è un algoritmo di ordinamento per numeri interi che sfrutta le singole cifre.
Per questo algoritmo partiamo subito con un esempio.
Esempio
Supponiamo di voler ordinare un array contenente elementi di valore tra 100 e 999.
A = [329, 457, 657, 839, 436]
Quello che fa il radix sort è di ordinare prima i numeri rispetto alle unità, al passo successivo rispetto alle decine ed unità e al passo finale rispetto alle centinaia, decine ed unità.
Per ordinare, questo algoritmo si serve di un altro algoritmo stabile, ovvero che non cambia di posizione due elementi con stesso valore.
L’algoritmo migliore per questo scopo è il counting sort, perché è stabile e garantisce l’ordinamento degli elementi in tempo lineare se il numero degli elementi da ordinare è maggiore o uguale al range di appartenza dei valori di tali elementi. Abbiamo approfondito questo concetto nel nostro articolo sul counting sort. Quindi lo pseudocodice è il seguente:
RadixSort(A, d):
for i=1 to d
CountingSort(A, i) //i -> i-esima cifra su d cifre Complessità O(d(n+k)) perché ordina per ogni serie di cifre (d cifre), n+k elementi.