Radix Sort in Java

1. Introduzione

In questo tutorial, impareremo a conoscere Radix Sort, ne analizzeremo le prestazioni e daremo un'occhiata alla sua implementazione.

Qui ci concentriamo sull'uso di Radix Sort per ordinare gli interi, ma non è limitato ai soli numeri. Possiamo usarlo per ordinare anche altri tipi come String .

Per mantenerlo semplice, ci concentreremo sul sistema decimale in cui i numeri sono espressi in base (radice) 10.

2. Panoramica dell'algoritmo

L'ordinamento radicale è un algoritmo di ordinamento che ordina i numeri in base alla posizione delle loro cifre. Fondamentalmente, utilizza il valore di posizione delle cifre in un numero. A differenza della maggior parte degli altri algoritmi di ordinamento, come Merge Sort, Insertion Sort, Bubble Sort, non confronta i numeri.

L'ordinamento digitale utilizza un algoritmo di ordinamento stabile come subroutine per ordinare le cifre. Abbiamo usato una variazione del conteggio dell'ordinamento come subroutine qui che usa la radice per ordinare le cifre in ogni posizione. Il conteggio dell'ordinamento è un algoritmo di ordinamento stabile e funziona bene nella pratica.

L'ordinamento digitale funziona ordinando le cifre dalla cifra meno significativa (LSD) alla cifra più significativa (MSD). Possiamo anche implementare l'ordinamento Radix per elaborare cifre da MSD.

3. Un rapido esempio

Vediamo come funziona con un esempio. Consideriamo il seguente array:

Iterazione 1:

Ordineremo questo array elaborando le cifre dall'LSD e spostandoci verso l'MSD.

Quindi iniziamo con le cifre in un posto:

Dopo la prima iterazione, l'array ora ha il seguente aspetto:

Notare che i numeri sono stati ordinati in base alle cifre in una posizione.

Iterazione 2:

Passiamo alle cifre al posto delle decine:

Ora l'array ha questo aspetto:

Vediamo che il numero 7 ha occupato la prima posizione nella matrice poiché non ha alcuna cifra al posto delle decine. Potremmo anche pensare che questo abbia uno 0 al posto delle decine.

Iterazione 3:

Passiamo alle cifre nella posizione delle centinaia:

Dopo questa iterazione, l'array avrà il seguente aspetto:

E l'algoritmo si ferma qui, con tutti gli elementi ordinati.

4. Implementazione

Vediamo ora l'implementazione.

void sort(int[] numbers) { int maximumNumber = findMaximumNumberIn(numbers); int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber); int placeValue = 1; while (numberOfDigits-- > 0) { applyCountingSortOn(numbers, placeValue); placeValue *= 10; } }

L'algoritmo funziona scoprendo il numero massimo nell'array e quindi calcolandone la lunghezza. Questo passaggio ci aiuta a garantire che eseguiamo la subroutine per ogni valore di posizione.

Ad esempio, nella matrice, [7, 37, 68, 123, 134, 221, 387, 468, 769] , il numero massimo è 769 e la sua lunghezza è 3.

Quindi, iteriamo e applichiamo la subroutine tre volte sulle cifre in ogni posizione:

void applyCountingSortOn(int[] numbers, int placeValue) { int range = 10 // decimal system, numbers from 0-9 // ... // calculate the frequency of digits for (int i = 0; i < length; i++) { int digit = (numbers[i] / placeValue) % range; frequency[digit]++; } for (int i = 1; i 
    
     = 0; i--) { int digit = (numbers[i] / placeValue) % range; sortedValues[frequency[digit] - 1] = numbers[i]; frequency[digit]--; } System.arraycopy(result, 0, numbers, 0, length); }
    

Nella subroutine, abbiamo usato la radice (intervallo) per contare l'occorrenza di ogni cifra e incrementarne la frequenza. Quindi, ogni bin nell'intervallo da 0 a 9 avrà un valore basato sulla frequenza delle cifre. Quindi usiamo la frequenza per posizionare ogni elemento nell'array. Questo ci aiuta anche a ridurre al minimo lo spazio necessario per ordinare l'array.

Ora testiamo il nostro metodo:

@Test public void givenUnsortedArray_whenRadixSort_thenArraySorted() { int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort(numbers); int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals(numbersSorted, numbers); }

5. Radix Sort vs Counting Sort

Nella subroutine, la lunghezza della matrice di frequenza è 10 (0-9). Nel caso di Counting Sort, non utilizziamo l' intervallo . La lunghezza dell'array di frequenza sarà il numero massimo nell'array + 1. Quindi non li dividiamo in bin mentre Radix Sort usa i bin per ordinare.

L'ordinamento conteggio è abbastanza efficiente quando la lunghezza dell'array non è molto inferiore al valore massimo nell'array, mentre l'ordinamento radicale consente valori più grandi nell'array.

6. Complessità

Le prestazioni di Radix Sort dipendono dall'algoritmo di ordinamento stabile scelto per ordinare le cifre.

Qui abbiamo usato Radix Sort per ordinare un array di n numeri in base b . Nel nostro caso, la base è 10. Abbiamo applicato l'ordinamento conteggio d volte dove d sta per il numero di cifre. Quindi la complessità temporale di Radix Sort diventa O (d * (n + b)) .

La complessità dello spazio è O (n + b) poiché qui abbiamo usato una variazione di Counting Sort come subroutine.

7. Conclusione

In questo articolo, abbiamo descritto l'algoritmo di ordinamento Radix e illustrato come implementarlo.

Come al solito, le implementazioni del codice sono disponibili su Github.