Ordinamento in tempo lineare: si può ! --- Parte 2 di 3: Radix Sort

Radix sort veniva utilizzato per ordinare le schede perforate, ordinando le schede in base alla loro cifra MENO significativa, separandole in “contenitori”, procedendo poi con la seconda cifra meno significativa, fino a fare r passaggi, dove r è il numero di CIFRE che compongono gli elementi.

Ci vogliono quindi r passaggi, ma ad ogni passaggio bisogna ordinare l'insieme di dati in base alla i-esima cifra meno significativa.

Serve quindi un algoritmo di ordinamento “ausiliario”, che deve essere – tra le altre cose – stabile; il counting sort, esaminato precedentemente, si presta bene allo scopo.

Lo pseudocodice dell'algoritmo è, quindi, banalissimo:

RADIX-SORT(A,r)

for(i=1 to r) fai-un-ordinamento-stabile-di-A-sulla-cifra-i

E' possibile dimostrare che, se l'algoritmo di ordinamento stabile impiega tempo O(n+k), con n numero di elementi da ordinare e k numero di valori che ciascun elemento può assumere (es.: per i numeri da 0 a 9, tale valore è 10), allora radix sort impiega tempo O(r(n+k)).

Quando r è costante e k = O(n), radix sort viene eseguito in tempo lineare.

Radix sort è utile per effettuare l'ordinamento di collezioni di elementi caratterizzati da più campi-chiave, come ad esempio le date (a patto di porre l'anno, equivalente alla cifra più significativa, a sinistra, scrivendo la data nella forma AAAA/MM/GG), che utilizzerò per mostrare, appunto, un esempio:

Da notare l'importanza della proprietà di stabilità dell'algoritmo che ordina le varie colonne, in presenza di valori duplicati (seguire, ad esempio, la coppia “2008”), specialmente in presenza di dati “satellite” associati alle varie date.