La versione classica esamina tutte le d cifre e, per ogni cifra, n elementi più b contenitori: Θ(d(n+b)).
Algoritmi di ordinamento · 6/7
Radix sort (LSD)
Ordina dalla cifra meno significativa usando passaggi stabili.
Tempo medioΘ(d(n + b))
MemoriaΘ(n + b)
StabileSì
In placeNo
Come funziona
L’LSD radix sort raggruppa prima per unità, poi decine, centinaia e così via. La stabilità di ogni passaggio conserva l’ordine già ottenuto sulle cifre meno significative.
Invariante: Dopo il passaggio sulla posizione exp, l’array è ordinato rispetto alle cifre da quella meno significativa fino a exp.
Simulazione passo passo
Ogni barra rappresenta un elemento. I colori distinguono gli elementi confrontati, il pivot o la chiave, la parte già definitiva e l’area attiva.
Da 2 a 16 valori. Per questo simulatore sono ammessi valori da 0 a 999.
- Confronti
- 0
- Scritture
- 0
- Scambi
- 0
- Passaggio / livello
- 0
attivo
confronto
pivot / chiave
definitivo
Pseudocodice collegato alla simulazione
exp ← 1while max(A) / exp > 0stably sort by digit (value / exp) mod 10distribute values into queues 0 … 9concatenate queues in orderexp ← exp · 10
La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.
Studio della complessità
L’ordine iniziale non cambia il numero di passaggi: Θ(d(n+b)).
Per chiavi di al più d cifre il limite resta Θ(d(n+b)); se d cresce, va mantenuto nel risultato.
Un passaggio stabile richiede Θ(n+b) memoria. La stabilità è indispensabile alla correttezza della variante LSD.
Proprietà in breve
La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.
La classificazione considera la versione dell’algoritmo mostrata in questa pagina.
Quando usarlo e che cosa evitare
Buona scelta quando…
Adatto a interi non negativi, identificatori e stringhe con numero di cifre limitato. La simulazione usa base 10.
Errore comune
Usare un ordinamento non stabile per una cifra cancella il lavoro dei passaggi precedenti. Segno e lunghezze variabili richiedono una gestione esplicita.