Radix sort
Il radix sort è l'eccezione tra gli algoritmi di ordinamento: non chiede mai quale di due valori sia più grande. Legge i numeri cifra per cifra e li ordina una cifra alla volta, usando dieci secchi. L'idea è più antica dei computer: è così che funzionavano le macchine per ordinare le schede perforate.
L'idea
Ordina i numeri solo per la cifra delle unità. Poi ordinali per la cifra delle decine, ma in modo che i numeri con la stessa cifra delle decine restino nell'ordine dato dalla prima passata. Poi per le centinaia, allo stesso modo. Dopo l'ultima passata la lista è ordinata: le centinaia decidono per prime, a parità di centinaia i numeri sono già in ordine di decine, e a parità di decine in ordine di unità.
Una passata, con i secchi
Ogni passata usa dieci secchi, uno per ogni cifra da 0 a 9. Scorri la lista dall'inizio alla fine e sposta ogni numero nel secchio della sua cifra, dietro i numeri già presenti. Poi svuota i secchi nella lista in ordine, prima il secchio 0. È proprio spostare i numeri nell'ordine della lista e aggiungerli in fondo a un secchio che rende stabile la passata. L'app conta prima i numeri per ogni cifra, così i secchi possono stare uno accanto all'altro in una sola riga, ognuno subito dopo il precedente: è un counting sort su una cifra.
Un esempio
Prendi 170, 45, 75, 90, 802, 24, 2, 66. Per la cifra delle unità: 170, 90, 802, 2, 24, 45, 75, 66. Per la cifra delle decine: 802, 2, 24, 45, 66, 170, 75, 90; nota che 802 e 2, entrambi con cifra delle decine 0, mantengono l'ordine della prima passata. Per la cifra delle centinaia: 2, 24, 45, 66, 75, 90, 170, 802. Tre passate su otto numeri: 24 cifre lette e 48 spostamenti, e nemmeno un confronto.
Quanto è veloce?
Ogni passata legge una cifra di ogni numero e sposta ogni numero due volte, quindi per n numeri di d cifre il lavoro cresce con n · d. Un ordinamento per confronto richiede almeno circa n log₂ n confronti nel caso peggiore, perché deve distinguere n! ordini possibili con una domanda sì o no alla volta. Il radix sort non ha questo limite, perché non pone mai domande del genere. Con molte chiavi corte, come un milione di numeri sotto 1.000, tre passate sono molto meno lavoro dei circa 20 milioni di confronti che servirebbero a un ordinamento per confronto. Con chiavi lunghe o pochi valori, il vantaggio sparisce.
LSD e MSD, e un po' di storia
La versione mostrata qui parte dalla cifra meno significativa (LSD). Al contrario, partendo dalla cifra più significativa (MSD), si divide la lista in secchi in base alla prima cifra e si ordina ogni secchio a parte, il che si adatta a stringhe di lunghezza diversa. Il radix sort risale alle ordinatrici di schede perforate nate dopo le macchine tabulatrici di Herman Hollerith per il censimento statunitense del 1890: un'ordinatrice faceva cadere ogni scheda in una di dieci caselle in base al foro in una colonna, e gli operatori facevano passare il mazzo una volta per colonna, partendo dall'ultima.
Provalo
Apri l'app e premi Passo. Ogni passata conta prima le cifre, delimitando i secchi da 0 a 9 nella riga sotto la lista. Poi i numeri cadono uno a uno nei loro secchi, con il secchio attivo evidenziato, e vengono ricopiati. Inserisci i tuoi numeri fino a 999, come l'esempio qui sopra, per vedere tutte e tre le passate.
Domande frequenti
Qual è la complessità temporale del radix sort?
O(n · d) per n chiavi di d cifre in una base fissa, più il costo dei secchi a ogni passata. Richiede O(n) memoria aggiuntiva per il buffer che contiene i secchi.
Il radix sort è stabile?
Il radix sort LSD deve esserlo: funziona solo perché ogni passata mantiene i valori con la stessa cifra nell'ordine in cui sono arrivati. Quindi anche il risultato finale è stabile.
Il radix sort può gestire numeri negativi o decimali?
Non direttamente, ma con un trucco sì: trasla i numeri negativi in modo che siano tutti positivi, oppure ordinali a parte e invertine l'ordine. I numeri in virgola mobile si possono ordinare in base ai loro schemi di bit dopo una piccola trasformazione.
Perché la base 10?
Perché è facile da seguire. I computer di solito ordinano 8 o 16 bit alla volta, quindi un numero a 32 bit richiede quattro o due passate, con 256 o 65.536 secchi.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il radix sort