Implementazioni di algoritmi/Radix sort: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Javificato!
Per ora ci penso io
Riga 1:
<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">