Implementazioni di algoritmi/Radix sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Modifico Categoria:Algoritmi |
m Bot: Aggiungo: en:Algorithm implementation/Sorting/Radix sort |
||
Riga 50: | Riga 50: | ||
[[Categoria:Implementazioni di algoritmi| ]] |
[[Categoria:Implementazioni di algoritmi| ]] |
||
[[en:Algorithm implementation/Sorting/Radix sort]] |
Versione delle 18:17, 5 mar 2008
Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O(), dove è la lunghezza dell'array e è la media del numero di cifre degli 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.
Implementazione in Java
public class radixSort {
public static void radixSort(int[] arr){
if(arr.length == 0)
return;
int[][] np = new int[arr.length][2]; //matrice
int[] q = new int[256];
int i,j,k,l,f = 0;
for(k=0;k<4;k++){
for(i=0;i<(np.length-1);i++)
np[i][1] = i+1;
np[i][1] = -1;
for(i=0;i<q.length;i++)
q[i] = -1;
for(f=i=0;i<arr.length;i++){
j = ((255<<(k<<3))&arr[i])>>(k<<3);
if(q[j] == -1)
l = q[j] = f;
else{
l = q[j];
while(np[l][1] != -1)
l = np[l][1];
np[l][1] = f;
l = np[l][1];
}
f = np[f][1];
np[l][0] = arr[i];
np[l][1] = -1;
}
for(l=q[i=j=0];i<256;i++)
for(l=q[i];l!=-1;l=np[l][1])
arr[j++] = np[l][0];
}
}
}}
Altri progetti
- Wikipedia contiene una voce su questo algoritmo