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 \mathcal{O}(n (1 + {log (k) \over log (n) } ))

La precedente definizione è dimostrabile ricordando che ci sono log_n (k) = \mathcal{O}(log_n (k)) passate di Integer sort e ciascuna richiede tempo \mathcal{O}(n).

Usando le regole per il cambiamento di base dei logaritmi, il tempo totale è dato da \mathcal{O}(n log_n (k)) = \mathcal{O}(n {log (k) \over log (n)}).

A questa quantità va aggiunto \mathcal{O}(n) per contemplare il caso in cui k < n, dato che la sequenza, va almeno letta.

[modifica] Altri progetti

Estratto da "http://it.wikipedia.org/wiki/Radix_sort"
Strumenti personali