Radix sort
Da Wikipedia, l'enciclopedia libera.
Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O(n * logk), dove n è la lunghezza dell'array e k è la media del numero di cifre degli n numeri.
Radixsort 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.
[modifica] Considerazioni sull'algoritmo
L'algoritmo Radix sort ha complessità computazionale variabile in base al valore k. Se k risulta essere minore di n, non si ha guadagno rispetto a Integer sort che opera in tempo lineare.
Se k è invece maggiore di 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 B = Θ(n) 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 k < n, dato che la sequenza, va almeno letta.
[modifica] Altri progetti
- Wikibooks contiene implementazioni di Radix sort
Algoritmi di ordinamento | ||
---|---|---|
Teoria | Teoria della complessità computazionale | Notazione O Grande | Lista | Stack | Coda | |
Algoritmi a scambio | Bubble sort | Cocktail sort | Comb sort | Gnome sort | Quicksort | |
Algoritmi di selezione | Selection sort | Heapsort | Smoothsort | |
Algoritmi ad inserimento | Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting | |
Algoritmi a fusione | Merge sort | |
Algoritmi non comparativi | Radix sort | Bucket sort | Counting sort | Pigeonhole sort | |
Altri algoritmi | Stupid sort |