Radix sort

Il radix sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O(${\displaystyle nk}$), dove ${\displaystyle n}$ è la lunghezza dell'array e ${\displaystyle k}$ è la media del numero di cifre degli ${\displaystyle n}$ numeri.

Radix sort
Esempio di funzionamento dell'algoritmo.
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	${\displaystyle O(kN)}$
Caso peggiore spazialmente	${\displaystyle O(kN)}$
Ottimale	Dipende dai dati

Radix sort utilizza un procedimento controintuitivo per l'uomo, ma più facilmente implementabile. Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno significativa. Questo affinché l'algoritmo non si trovi a dovere operare ricorsivamente su sottoproblemi di dimensione non valutabili a priori.

Considerazioni sull'algoritmo

L'algoritmo radix sort ha complessità computazionale variabile in base al valore ${\displaystyle k}$. Se ${\displaystyle k}$ risulta essere minore di ${\displaystyle n}$, non si ha guadagno rispetto a counting sort che opera in tempo lineare.

Se ${\displaystyle k}$ è invece maggiore di ${\displaystyle n}$, l'algoritmo può risultare peggiore anche dei più classici algoritmi di ordinamento per confronto a tempo quasi lineare, come quicksort o mergesort.

Usando come base dell'algoritmo un valore ${\displaystyle B=\Theta (n)}$ il tempo di ordinamento diviene ${\displaystyle {\mathcal {O}}\left(n\left(1+{\log(k) \over \log(n)}\right)\right)}$

La precedente definizione è dimostrabile ricordando che ci sono ${\displaystyle \log _{n}(k)={\mathcal {O}}(\log _{n}(k))}$ passate di Integer sort e ciascuna richiede tempo ${\displaystyle {\mathcal {O}}(n)}$.

Usando le regole per il cambiamento di base dei logaritmi, il tempo totale è dato da ${\displaystyle {\mathcal {O}}(n\log _{n}(k))={\mathcal {O}}\left(n{\log(k) \over \log(n)}\right)}$.

A questa quantità va aggiunto ${\displaystyle {\mathcal {O}}(n)}$ per contemplare il caso in cui ${\displaystyle k<n}$, dato che la sequenza va almeno letta.

Pseudocodice

Ogni elemento nell'array ${\displaystyle A}$ di ${\displaystyle n}$ elementi ha ${\displaystyle d}$ cifre, dove ${\displaystyle 1}$ è la cifra di ordine più basso e ${\displaystyle d}$ quella di ordine più alto.

Radix-sort (A, d)
   for i <- 1 to d
       do usa un ordinamento stabile per ordinare l'array A sulla cifra i

Storia

Origini

L'idea fondamentale del radix sort fu originariamente applicata alle macchine di smistamento a schede perforate, sviluppate da Herman Hollerith alla fine del XIX secolo. Queste macchine furono impiegate per il censimento degli Stati Uniti del 1890, dimostrando un'efficienza notevole nella gestione e nell'ordinamento di grandi volumi di dati. Le schede perforate, tipicamente formate da 80 colonne, potevano essere perforate in una delle 12 posizioni disponibili per ciascuna colonna, consentendo la codifica di numeri, lettere e simboli.

Il processo di ordinamento manuale o semi-meccanico sulle schede perforate seguiva la logica del radix sort: le schede venivano smistate ripetutamente in base a cifre successive, partendo da quella meno significativa (LSD, Least Significant Digit) fino ad arrivare a quella più significativa (MSD, Most Significant Digit). Per ogni passaggio, le schede venivano distribuite in scomparti corrispondenti al valore della cifra corrente e poi raccolte, mantenendo l'ordine relativo acquisito nei passaggi precedenti. Le aziende fondate da Hollerith, che in seguito confluirono in IBM, furono pioniere nell'utilizzo e nello sviluppo di queste tecniche.

Sviluppi Informatici

L'algoritmo del radix sort fu formalizzato e analizzato nel contesto dei calcolatori elettronici da Harold H. Seward nel 1954, attraverso il suo rapporto tecnico Information sorting in the A-2 computer del MIT. Il lavoro di Seward adattò i principi di ordinamento delle schede perforate all'architettura e alle capacità dei computer emergenti, dimostrando la possibilità di un ordinamento efficiente anche in questo nuovo contesto.

Nonostante l'affermazione di altri algoritmi di ordinamento basati sui confronti (come Quicksort e Mergesort), il radix sort mantiene la sua rilevanza, specialmente per l'ordinamento di numeri interi o stringhe con un intervallo di valori limitato. La sua caratteristica di essere un algoritmo non-comparativo gli permette di raggiungere una complessità temporale di O(nk) nel caso peggiore, dove n è il numero di elementi e k è il numero di cifre (o passaggi), rendendolo potenzialmente più veloce per specifici tipi di dati rispetto agli algoritmi O(nlogn).

Bibliografia

• (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 4ª ed., MIT Press, 2022, ISBN 978-0-262-04630-5.

• (EN) P. E. T., The Story of Computing, Oxford University Press, 1995.

Altri progetti

Altri progetti

• Wikibooks
• Wikimedia Commons

• Wikibooks contiene implementazioni del radix sort
• Wikimedia Commons contiene immagini o altri file sul radix sort

Collegamenti esterni

• (EN) Eric W. Weisstein, Radix Sort, su MathWorld, Wolfram Research.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica