Implementazioni di algoritmi/Radix sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Modifico: en:Algorithm Implementation/Sorting/Radix sort |
m Update syntaxhighlight tags - remove use of deprecated <source> tags |
||
Riga 7: | Riga 7: | ||
==Implementazione in Java== |
==Implementazione in Java== |
||
< |
<syntaxhighlight lang="java"> |
||
public class radixSort { |
public class radixSort { |
||
public static void radixSort(int[] arr){ |
public static void radixSort(int[] arr){ |
||
Riga 42: | Riga 42: | ||
} |
} |
||
}} |
}} |
||
</syntaxhighlight> |
|||
</source> |
|||
== Altri progetti == |
== Altri progetti == |
Versione attuale delle 07:04, 19 apr 2020
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[modifica]
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[modifica]
- Wikipedia contiene una voce su questo algoritmo