Implementazioni di algoritmi/Radix sort: differenze tra le versioni

Vai alla navigazione Vai alla ricerca

Implementazioni di algoritmi/Radix sort (modifica)

Versione delle 18:58, 14 set 2007

128 byte rimossi ,  16 anni fa
Per ora ci penso io
VisualeWikitesto
(Javificato!)
(Per ora ci penso io)
<noinclude>{{WIP|Fabrymondo}}</noinclude>
{{S|informatica}}
 
[[Immagine:Radix.JPG||thumb|right|450px|]]▼
Il '''Radix Sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità computazionale]] lineare [[o-grande|O]](<math>n *k 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 e pertanto è classificabile come O(n) (ovvero complessità lineare).
 
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.
L'idea base è quella di ordinare il vettore di numeri in ingresso, eseguendo confronti a partire dalle cifre meno significative (le unità), salendo via via a quelle più significative (decine, centinaia, migliaia, ecc.).
 
'''===Algoritmo in Java'''===▼
L'algoritmo può essere implementato in maniera ricorsiva od iterativa; l'implementazione non è, però, semplice. Se ne propone una delle possibili implementazioni iterative scritte in Java.
 
 
== Esempio di Radix Sort ==
 
 
▲[[Immagine:Radix.JPG]]
 
 
▲'''Algoritmo in Java'''
 
<source lang="java">
Fabrymondo
1

contributo

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

Menu di navigazione