Implementazioni di algoritmi/Radix sort

Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O($n*logk$), dove $n$ è la lunghezza dell'array e $k$ è la media del numero di cifre degli $n$ 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.

Considerazioni sull'algoritmo

L'algoritmo Radix sort ha complessità computazionale variabile in base al valore k. Se k risulta essere minore di n, non si ha guadagno rispetto a Integer sort che opera in tempo lineare.

Se k è invece maggiore di n, l'algoritmo può risultare peggiore anche dei più classici algoritmi di ordinamento per confronto a tempo quasi lineare, come Quicksort o Mergesort.

Usando come base dell'algoritmo un valore B = Θ(n) il tempo di ordinamento diviene ${\mathcal {O}}(n(1+{log(k) \over log(n)}))$

La precedente definizione è dimostrabile ricordando che ci sono $log_{n}(k)={\mathcal {O}}(log_{n}(k))$ passate di Integer sort e ciascuna richiede tempo ${\mathcal {O}}(n)$.

Usando le regole per il cambiamento di base dei logaritmi, il tempo totale è dato da ${\mathcal {O}}(nlog_{n}(k))={\mathcal {O}}(n{log(k) \over log(n)})$.

A questa quantità va aggiunto ${\mathcal {O}}(n)$ per contemplare il caso in cui k < n, dato che la sequenza, va almeno letta.

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];
   }
  }
 }}