Radix sort
Radix sort | |
---|---|
Esempio di funzionamento dell'algoritmo. | |
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | |
Caso peggiore spazialmente | |
Ottimale | Dipende dai dati |
Il radix sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O(), dove è la lunghezza dell'array e è la media del numero di cifre degli 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.
Considerazioni sull'algoritmo
[modifica | modifica wikitesto]L'algoritmo radix sort ha complessità computazionale variabile in base al valore . Se risulta essere minore di , non si ha guadagno rispetto a counting sort che opera in tempo lineare.
Se è invece maggiore di , 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 il tempo di ordinamento diviene
La precedente definizione è dimostrabile ricordando che ci sono passate di Integer sort e ciascuna richiede tempo .
Usando le regole per il cambiamento di base dei logaritmi, il tempo totale è dato da .
A questa quantità va aggiunto per contemplare il caso in cui , dato che la sequenza va almeno letta.
Pseudocodice
[modifica | modifica wikitesto]Radix-sort (A, d) for i <- 1 to d do usa un ordinamento stabile per ordinare l'array A sulla cifra i
Storia
[modifica | modifica wikitesto]Il radix sort è l'algoritmo utilizzato dalle macchine per ordinare le schede perforate, che adesso si trovano soltanto nei musei di calcolatori.
Altri progetti
[modifica | modifica wikitesto]- Wikibooks contiene implementazioni del radix sort
- Wikimedia Commons contiene immagini o altri file sul radix sort
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Eric W. Weisstein, Radix sort, su MathWorld, Wolfram Research.