Implementazioni di algoritmi/Radix sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m robot Aggiungo: no:Radikssortering |
m Bot: Sostituzione automatica fix vari |
||
Riga 3: | Riga 3: | ||
Il '''Radix Sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità]] lineare O(<math>n*k</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). |
Il '''Radix Sort''' è un [[algoritmo]] di ordinamento per valori numerici interi con [[complessità]] lineare O(<math>n*k</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). |
||
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 |
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.). |
||
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. |
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. |
Versione delle 10:35, 8 mag 2007
Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità lineare O(), dove è la lunghezza dell'array e è la media del numero di cifre degli numeri e pertanto è classificabile come O(n) (ovvero complessità lineare).
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.).
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
Algoritmo 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]; } } }}