Questa voce o sezione sull'argomento algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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
Manuale

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 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.

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.

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

• (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.

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

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

V · D · M Algoritmi di ordinamento
Teoria	Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo
Algoritmi a scambio	Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort
Algoritmi di selezione	Selection sort · Heap sort · Smoothsort
Algoritmi ad inserimento	Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting
Algoritmi a fusione	Merge sort · Timsort
Algoritmi non comparativi	Radix sort · Bucket sort · Counting sort · Pigeonhole sort
Altri algoritmi	Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle
Algoritmi inefficienti	Stupid sort · Trippel sort

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