Wikibooks

Implementazioni di algoritmi/Radix sort: differenze tra le versioni

Modulo Discussione

Implementazioni di algoritmi/Radix sort (modifica)

Versione delle 20:22, 4 mar 2008

1 479 byte rimossi ,  14 anni fa
link a pedia, template indice e interprogetto
m (ha spostato Radix sort a Algoritmi/Radix sort: convenzioni di nomenclatura)
(link a pedia, template indice e interprogetto)
{{algoritmi}}
Il '''Radix Sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità computazionale]] [[o-grande|O]](<math>n * logk</math>), dove <math>n</math> è la lunghezza dell'array e <math>k</math> è la media del numero di cifre degli <math>n</math> numeri.▼
 
[[Immagine:Radix.JPG||thumb|right|450px|]]
▲Il '''Radix Sort''' è un [[w:algoritmo|algoritmo]] di ordinamento per valori numerici interi con [[w:complessità computazionale|complessità computazionale]] [[w:o-grande|O]](<math>n * logk</math>), dove <math>n</math> è la lunghezza dell'array e <math>k</math> è la media del numero di cifre degli <math>n</math> 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.
 
==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 <math>\mathcal{O}(n (1 + {log (k) \over log (n) } ))</math>
 
La precedente definizione è dimostrabile ricordando che ci sono <math>log_n (k) = \mathcal{O}(log_n (k))</math> passate di [[Integer sort]] e ciascuna richiede tempo <math>\mathcal{O}(n)</math>.
 
Usando le regole per il cambiamento di base dei [[logaritmo|logaritmi]], il tempo totale è dato da <math>\mathcal{O}(n log_n (k)) = \mathcal{O}(n {log (k) \over log (n)})</math>.
 
A questa quantità va aggiunto <math>\mathcal{O}(n)</math> per contemplare il caso in cui k < n, dato che la sequenza, va almeno letta.
 
==Implementazione in Java==
{{Trasferimento|wb|Implementazioni}}
 
<source lang="java">
</source>
 
== Altri progetti ==
{{interprogetto|w=Radix sort|w_etichetta=questo algoritmo}}
 
[[Categoria:Algoritmi| di ordinamento]]
{{Avanzamento|100%|4 marzo 2008}}
 
[[cs:Radix sort]]
[[de:Radixsort]]
[[en:Radix sort]]
[[es:Ordenamiento Radix]]
[[fi:Kantalukulajittelu]]
[[fr:Tri par base]]
[[he:מיון בסיס]]
[[ja:基数ソート]]
[[ko:기수 정렬]]
[[lt:Skaitmeninis rikiavimo algoritmas]]
[[nl:Radix sort]]
[[no:Radikssortering]]
[[pl:Sortowanie pozycyjne]]
[[pt:Radix sort]]
[[ru:Поразрядная сортировка]]
[[uk:Сортування за розрядами]]
[[vi:Sắp xếp theo cơ số]]
[[zh:基数排序]]
Baruneju
61

contributi

Estratto da "https://it.wikibooks.org/wiki/Speciale:DiffMobile/114037"