Implementazioni di algoritmi/Radix sort: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
m robot Aggiungo: de, en, es, fi, fr, he, ja, lt, nl, pt, zh
Riga 63: Riga 63:
[[nl:Radix sort]]
[[nl:Radix sort]]
[[pt:Radix sort]]
[[pt:Radix sort]]
[[ru:Поразрядная сортировка]]
[[zh:基数排序]]
[[zh:基数排序]]

Versione delle 06:17, 13 giu 2006

Template:Stub informatica Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità lineare O(), dove n è la lunghezza dell'array, d è la base di rappresentazione del numero da ordinare e k è il numero di digit (cifre) del numero.

?L'idea base è quella di ordinare il vettore di numeri in ingresso, eseguendo confronti a partire dalle cifre più significative (le unità), salendo via via a quelle meno 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];
  }
 }
}}