Dede Blog: just another Software Development Engineer

Radix Sort è un algoritmo di ordinamento non basato sul confronto degli elementi da ordinare. Prevede invece di ordinare gli elementi, nella sua versione cosiddetta LSD (Least significant digit) partendo con l’analisi della cifra meno significativa e raggruppando gli elementi in dei “contenitori”, generalmente chiamati buckets, in base al valore di tale cifra. Avremo quindi un bucket per ogni cifra da 0 a 9 in cui verrano inseriti gli elementi a seconda del valore della loro cifra meno significativa. Una cosa fondamentale da notare è che, all’interno di ciascun bucket, gli elementi vengono inseriti in ordine di apparizione all’interno dell’array da ordinare.
Per determinare in quale bucket un elemento deve essere inserito si utilizzano due variabili di supporto che chiamiamo ‘n‘ ed ‘m‘ e l’operazione per ottenere il bucket per l’elemento ‘e‘ è: (e % m) / n. Ma su questo punto torneremo tra poco quando vedremo in dettaglio un esempio concreto di esecuzione dell’algoritmo.
Una volta assegnato ciascun elemento ad un bucket, si crea il nuovo array risultante dalla prima iterazione, “svuotando” i bucket in modo ordinato dal primo (0) all’ultimo (9) e mantenendo l’ordine di inserimento all’interno del singolo bucket ed i buckets vengono ripuliti. A questo punto ci si sposta sulla cifra successiva, la seconda meno significativa e si esegue la stessa operazione di raggruppamento e di generazione del nuovo array. Ripetendo il procedimento fino alla cifra più significativa del più “lungo” dei numeri, si ottiene l’array finale ordinato.

Ma vediamo un esempio illustrato graficamente.
Supponiamo di dover ordinare l’array contenente i valori: 99, 23, 55, 15, 3, 354, 9, 134, 65, 10, 100, 234, 107
Come detto dobbiamo, ad ogni iterazione, inserire ogni elemento in un bucket, in base al valore della cifra che stiamo considerando. Partiamo dalla cifra meno significativa ed iniziamo a processare il primo elemento, partendo con le variabili n ed m inizializzate rispettivamente a 1 e 10. Il valore è 99 per cui calcoliamo:

99 % m = 9
9 / n = 9

L’elemento 99, avendo 9 come cifra meno significativa, finisce nel bucket 9.

procediamo con il secondo elemento, 23, calcolando:

23 % m = 3
3 / n = 3

l’elemento 23 finisce quindi correttamente nel bucket 3 (avendo 3 come cifra meno significativa). Andando avanti con il procedimento per tutti gli elementi dell’array, al termine della prima iterazione otteniamo il risultato illustrato nella figura seguente.

Per ottenere l’array risultante dalla prima iterazione, come detto in apertura, dobbiamo prendere gli elementi partendo dal bucket 0 fino al bucket 9, rispettando l’ordine con cui sono stati inseriti (cioè in base all’ordine in cui comparivano).
Otteniamo quindi il nuovo array: 10, 100, 23, 3, 354, 134, 234, 55, 15, 65, 107, 99, 9

A questo punto dobbiamo svuotare i buckets e procedere con l’analisi della seconda cifra meno significativa. Per farlo dobbiamo aggiornare le nostre variabili n ed m in modo che calcolino il bucket di destinazione in base alla cifra del nostro elemento che rappresenta le decine. Moltiplichiamo quindi entrambe le variabili per 10 ed otteniamo i valori n = 10 e m = 100.

Il primo elemento da processare del nuovo array è 10, per cui calcoliamo:

10 % m = 10
10 / n = 1

L’elemento 10 finisce nel bucket 1 ed è corretto, in quanto presenta 1 come valore della seconda cifra meno significativa.
Ancora una volta eseguiamo lo stesso procedimento per tutti gli elementi dell’array ed otteniamo, al termine di questa seconda iterazione, la situazione seguente:

Nuovamente partiamo dal primo bucket e, seguendo l’ordine, creiamo il nuovo array prodotto da questa iterazione: 100, 3, 107, 9, 10, 15, 23, 134, 234, 354, 55, 65, 99

Procediamo ulteriormente analizzando la successiva cifra meno significativa, quella delle centinaia. Aggiorniamo a tale scopo i valori delle nostre variabili di supporto, moltiplicandole nuovamente per 10 ed ottenendo quindi i valori n = 100 e m = 1000.

Ripetiamo il processo di assegnamento degli elementi ai buckets. Il primo elemento del nuovo array è 100 per cui calcoliamo:

100 % m = 100
100 / n = 1

L’elemento 100 finisce ora nel bucket 1 (avendo 1 come terza cifra meno significativa).

Al termine dell’intera iterazione sulla cifra corrente otteniamo la situazione seguente:

Avendo nel nostro array al massimo elementi composti da 3 cifre, con questa iterazione abbiamo terminato il processo. L’array ottenuto con il solito processo di scodamento degli elementi dai buckets è a questo punto il nostro array finale ordinato: 3, 9, 10, 15, 23, 55, 65, 99, 100, 107, 134, 234, 354

Dall’analisi di questo processo si deduce facilmente che la complessità in tempo del Radix Sort è data da O(nk) dove n è il numero degli elementi da ordinare e k è il numero di cifre che compone il più lungo degli elementi.

Ora che abbiamo descritto il suo funzionamento, possiamo passare ad implementare l’algoritmo Radix Sort in Java.

Per prima cosa individuiamo la struttura dati che ci serve per rappresentare il nostro array associativo. Come detto che ci serve un array contenente le liste di elementi appartenenti ad ogni “gruppo”, per cui possiamo optare per una cosa tipo:

private List> buckets = new ArrayList<>();

Abbiamo quindi definito come variabile d’istanza della nostra classe RadixSort un ArrayList di LinkedList contenenti valori interi. In alternativa, avremmo anche potuto utilizzare un semplice array al posto della collection ArrayList. Una volta definita la struttura, dobbiamo procedere con la sua inizializzazione, cioè con la creazione di una LinkedList di interi per ogni bucket, quindi per ciascuno degli elementi dell’ArrayList da 0 a 9. Affidiamo questo al compito al costruttore della nostra classe:

public RadixSort() {
   for (int i = 0; i<10; i++) {
      this.buckets.add(new LinkedList());
   }
}

Nel main della classe definiamo quelli che saranno gli input del nostro algoritmo e cioè:
– l’array di interi contenente gli elementi da ordinare
– un intero che ci indica qual è il numero massimo di cifre da cui sono composti i nostri elementi

A questo punto il nostro codice si presenta quindi come segue, con l’invocazione del metodo sort() sull’istanza della nostra classe RadixSort e con il prototipo del metodo che accetta i due parametri appena descritti:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class RadixSort {

    private List> buckets = new ArrayList<>();

    public RadixSort() {
        for (int i = 0; i<10; i++) {
            this.buckets.add(new LinkedList());
        }
    }

    public void sort(int[] ar, int maxl) {
        // implementare logica Radix Sort
    }

    public static void main(String[] args){
        final int[] elements = { 99, 23, 55, 15, 3, 354, 9, 134, 65, 10, 100, 234, 107};
        final int maxLength = 3;	 // abbiamo al massimo numeri di 3 cifre
        RadixSort rs = new RadixSort();
	rs.sort(elements, 3);
    }
}

Non ci resta che implementare la logica del RadixSort.
Iniziamo con il dichiarare ed inizializzare le variabili ‘n’ ed ‘m’ necessarie per implementare la logica per il calcolo del bucket in cui andare ad inserire l’elemento.
Poi calcoliamo questo valore per ciascun elemento dell’array ed andiamo ad inserirlo nel bucket corretto. Aggiungiamo anche un stampa in output di debug per verificare.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class RadixSort {

    private List> buckets = new ArrayList<>();

    public RadixSort() {
        for (int i = 0; i<10; i++) {
            this.buckets.add(new LinkedList());
        }
    }

    public void sort(int[] ar, int maxl) {
        int n=1;
        int m=10;
        for (int i : ar)
        {
            int tmp = (i%m)/n;
            this.buckets.get(tmp).add(i);
            System.out.println("Elemento " + i + " nel bucket " + tmp);
	}
    }

    public static void main(String[] args){
        final int[] elements = { 99, 23, 55, 15, 3, 354, 9, 134, 65, 10, 100, 234, 107};
        final int maxLength = 3;	// abbiamo al massimo numeri di 3 cifre
        RadixSort rs = new RadixSort();
	rs.sort(elements, 3);
    }
}

Provando ad eseguire il programma otteniamo il seguente output:

Elemento 99 nel bucket 9
Elemento 23 nel bucket 3
Elemento 55 nel bucket 5
Elemento 15 nel bucket 5
Elemento 3 nel bucket 3
Elemento 354 nel bucket 4
Elemento 9 nel bucket 9
Elemento 134 nel bucket 4
Elemento 65 nel bucket 5
Elemento 10 nel bucket 0
Elemento 100 nel bucket 0
Elemento 234 nel bucket 4
Elemento 107 nel bucket 7

A questo punto, prima di procedere con la definizione dell’algoritmo di ordinamento, andiamo a ridefine il metodo toString() della nostra classe RadixSort, in modo che ci restituisca una forma leggibile della situazione della nostra struttura dati e ci permetta di vedere le liste di elementi che sono stati inseriti nei rispettivi buckets.
Ridefiniamo quindi il metodo toString() nel modo seguente:

@Override
public String toString() {
   StringBuilder ret = new StringBuilder();
   int i = 0;
   for (LinkedList li : this.buckets){
      ret.append(i++).append(" -> ").append(li).append("\n");
   }
   return ret.toString();
}

ed andiamo a modificare il metodo sort() implementato finora affinchè ci mostri questa rappresentazione. Eliminiamo quindi la print inserita precedentemente all’interno del loop ed inseriamo invece come debug la stampa del nostro oggetto RadixSort:

public void sort(int[] ar, int maxl) {
	int n=1;
	int m=10;

	for (int i : ar)
	{
		int tmp = (i%m)/n;
		this.buckets.get(tmp).add(i);
	}

	System.out.println(this);
}

L’output questa volta è molto più esplicativo e ci riporta la situazione delle liste nella forma che avevamo utilizzato all’inizio, in fase di descrizione dell’algoritmo:

0 -> [10, 100]
1 -> []
2 -> []
3 -> [23, 3]
4 -> [354, 134, 234]
5 -> [55, 15, 65]
6 -> []
7 -> [107]
8 -> []
9 -> [99, 9]

Possiamo facilmente verificare che fino a questo punto sta funzionando tutto bene, in quanto tutti gli elementi appaiono nella lista del bucket relativo alla loro cifra meno significativa e che all’interno di ciascuna lista compaiono secondo l’ordine in cui apparivano nell’array originale.

Il prossimo step consiste nel creare, a partire dalle liste dei vari buckets, il nuovo array di input per l’iterazione successiva. Per farlo, come abbiamo visto, occorre scorrere le liste in ordine dal primo all’ultimo bucket e, per ciascuna, dal primo all’ultimo elemento.
Creiamo quindi un metodo che prende in input il nostro array di partenza e ci riordina gli elementi scorrendo le liste come appena visto:

private void createOutputArray(int[] ar){
   int i = 0;
   for (LinkedList li : this.buckets) {
      for (int k : li)
      {
         ar[i]=k;
	 i++;
      }
   }
}

Nel metodo sort() invochiamo questo nuovo metodo e poi ci facciamo stampare il nuovo array per verificare se il metodo ha effettuato correttamente l’operazione:

public void sort(int[] ar, int maxl) {
   int n=1;
   int m=10;
   for (int i : ar)
   {
      int tmp = (i%m)/n;
      this.buckets.get(tmp).add(i);
   }
   System.out.println(this);
   this.createOutputArray(ar);
   System.out.println("OUTPUT: " + Arrays.toString(ar));
}

L’output di questa nuova esecuzione è il seguente:

0 -> [10, 100]
1 -> []
2 -> []
3 -> [23, 3]
4 -> [354, 134, 234]
5 -> [55, 15, 65]
6 -> []
7 -> [107]
8 -> []
9 -> [99, 9]

OUTPUT: [10, 100, 23, 3, 354, 134, 234, 55, 15, 65, 107, 99, 9]

Dopo aver modificato gli elementi dell’array secondo il nuovo ordine, “svuotiamo” tutti i buckets in modo da prepararli per la nuova iterazione. Per farlo creiamo un altro metodo di supporto come segue:

private void clearBuckets(){
   for (int i = 0; i<10; i++) {
       this.buckets.get(i).clear();
   }
}

A questo punto il codice completo della nostra implementazione dell'algoritmo Radix Sort è il seguente:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class RadixSort {

    private List> buckets = new ArrayList<>();

    public RadixSort() {
        for (int i = 0; i<10; i++) {
            this.buckets.add(new LinkedList());
        }
    }

    @Override
    public String toString() {
	StringBuilder ret = new StringBuilder();
	int i = 0;
	for (LinkedList li : this.buckets){
	    ret.append(i++).append(" -> ").append(li).append("\n");
	}
	return ret.toString();
    }

    private void createOutputArray(int[] ar){
	int i = 0;
	for (LinkedList li : this.buckets) {
            for (int k : li)
            {
                ar[i]=k;
		i++;
            }
        }
    }

    private void clearBuckets(){
	for (int i = 0; i<10; i++) {
            this.buckets.get(i).clear();
        }
    }

    public void sort(int[] ar, int maxl) {
        for (int iter = 0, n = 1, m = 10; iter < maxl; iter++, n*=10, m*=10) {
            for (int i : ar)
            {
                int tmp = (i%m)/n;
                this.buckets.get(tmp).add(i);
            }
            System.out.println("----- ITERATION " + (iter+1) + " -----");
            System.out.println(this);
            this.createOutputArray(ar);
            System.out.println("OUTPUT: " + Arrays.toString(ar));
            System.out.println("----------------\n");
            this.clearBuckets();
        }
    }

    public static void main(String[] args){
        final int[] elements = { 99, 23, 55, 15, 3, 354, 9, 134, 65, 10, 100, 234, 107};
        //int[] elements = { 9, 179, 139,38,10, 5, 36};
        final int maxLength = 3;
        RadixSort rs = new RadixSort();
	rs.sort(elements, 3);
	System.out.println("SORTED ARRAY: " + Arrays.toString(elements));
    }
}

Provando ad eseguire il programma otteniamo il seguente output che mostra, per ogni iterazione, la situazione dei buckets in cui vengono inseriti gli elementi ed il nuovo array risultante. Al termine, viene mostrato l'array ordinato.

----- ITERATION 1 -----
0 -> [10, 100]
1 -> []
2 -> []
3 -> [23, 3]
4 -> [354, 134, 234]
5 -> [55, 15, 65]
6 -> []
7 -> [107]
8 -> []
9 -> [99, 9]

OUTPUT: [10, 100, 23, 3, 354, 134, 234, 55, 15, 65, 107, 99, 9]
----------------

----- ITERATION 2 -----
0 -> [100, 3, 107, 9]
1 -> [10, 15]
2 -> [23]
3 -> [134, 234]
4 -> []
5 -> [354, 55]
6 -> [65]
7 -> []
8 -> []
9 -> [99]

OUTPUT: [100, 3, 107, 9, 10, 15, 23, 134, 234, 354, 55, 65, 99]
----------------

----- ITERATION 3 -----
0 -> [3, 9, 10, 15, 23, 55, 65, 99]
1 -> [100, 107, 134]
2 -> [234]
3 -> [354]
4 -> []
5 -> []
6 -> []
7 -> []
8 -> []
9 -> []

OUTPUT: [3, 9, 10, 15, 23, 55, 65, 99, 100, 107, 134, 234, 354]
----------------

SORTED ARRAY: [3, 9, 10, 15, 23, 55, 65, 99, 100, 107, 134, 234, 354]