Radix Sort in Java

1. Einleitung

In diesem Tutorial lernen wir Radix Sort kennen, analysieren seine Leistung und werfen einen Blick auf seine Implementierung.

Hier konzentrieren wir uns auf die Verwendung von Radix Sort, um Ganzzahlen zu sortieren, aber es ist nicht nur auf Zahlen beschränkt. Wir können es auch verwenden, um andere Typen wie String zu sortieren .

Um es einfach zu halten, konzentrieren wir uns auf das Dezimalsystem, in dem die Zahlen in Basis (Radix) 10 ausgedrückt werden.

2. Algorithmusübersicht

Die Radix-Sortierung ist ein Sortieralgorithmus, der Zahlen anhand der Positionen ihrer Ziffern sortiert. Grundsätzlich wird der Stellenwert der Ziffern in einer Zahl verwendet. Im Gegensatz zu den meisten anderen Sortieralgorithmen wie Merge Sort, Insertion Sort und Bubble Sort werden die Zahlen nicht verglichen.

Die Radix-Sortierung verwendet einen stabilen Sortieralgorithmus als Unterprogramm zum Sortieren der Ziffern. Wir haben hier eine Variation der Zählsortierung als Unterroutine verwendet, die den Radix verwendet, um die Ziffern an jeder Position zu sortieren. Das Zählen der Sortierung ist ein stabiler Sortieralgorithmus und funktioniert in der Praxis gut.

Die Radix-Sortierung sortiert Ziffern von der kleinsten signifikanten Ziffer (LSD) bis zur höchstwertigen Ziffer (MSD). Wir können auch die Radix-Sortierung implementieren, um Ziffern aus MSD zu verarbeiten.

3. Ein kurzes Beispiel

Mal sehen, wie es mit einem Beispiel funktioniert. Betrachten wir das folgende Array:

Iteration 1:

Wir werden dieses Array sortieren, indem wir Ziffern von LSD verarbeiten und in Richtung MSD gehen.

Beginnen wir also mit den Ziffern an einer Stelle:

Nach der ersten Iteration sieht das Array nun folgendermaßen aus:

Beachten Sie, dass die Zahlen nach den Ziffern an einer Stelle sortiert wurden.

Iteration 2:

Gehen wir zu den Ziffern an zehn Stellen über:

Jetzt sieht das Array so aus:

Wir sehen, dass die Zahl 7 die erste Position im Array belegt hat, da sie an der Zehnerstelle keine Ziffer hat. Wir könnten uns das auch als eine 0 an der Zehnerstelle vorstellen.

Iteration 3:

Gehen wir zu den Ziffern in der Hunderterposition über:

Nach dieser Iteration sieht das Array folgendermaßen aus:

Und der Algorithmus stoppt hier, wobei alle Elemente sortiert sind.

4. Implementierung

Schauen wir uns nun die Implementierung an.

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

Der Algorithmus ermittelt die maximale Anzahl im Array und berechnet dann dessen Länge. Dieser Schritt hilft uns sicherzustellen, dass wir die Unterroutine für jeden Platzwert ausführen.

Beispielsweise beträgt in dem Array [7, 37, 68, 123, 134, 221, 387, 468, 769] die maximale Anzahl 769 und seine Länge 3.

Also iterieren wir und wenden das Unterprogramm dreimal auf die Ziffern an jeder Position an:

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

In der Unterroutine haben wir den Radix (Bereich) verwendet, um das Auftreten jeder Ziffer zu zählen und ihre Frequenz zu erhöhen. Daher hat jeder Behälter im Bereich von 0 bis 9 einen Wert, der auf der Häufigkeit der Ziffern basiert. Wir verwenden dann die Frequenz, um jedes Element im Array zu positionieren. Dies hilft uns auch, den zum Sortieren des Arrays erforderlichen Speicherplatz zu minimieren.

Testen wir nun unsere Methode:

@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

In der Unterroutine beträgt die Länge des Frequenzarrays 10 (0-9). Im Fall von Counting Sort verwenden wir den Bereich nicht . Die Länge des Frequenzarrays ist die maximale Anzahl im Array + 1. Wir teilen sie also nicht in Bins auf, während Radix Sort die Bins zum Sortieren verwendet.

Das Zählen der Sortierung ist sehr effizient, wenn die Länge des Arrays nicht viel kleiner als der Maximalwert im Array ist, während die Radix-Sortierung größere Werte im Array zulässt.

6. Komplexität

Die Leistung von Radix Sort hängt vom stabilen Sortieralgorithmus ab, der zum Sortieren der Ziffern ausgewählt wurde.

Hier haben wir die Radix-Sortierung verwendet, um ein Array von n Zahlen in Basis b zu sortieren . In unserem Fall ist die Basis 10. Wir haben die Zählsortierung d- mal angewendet, wobei d für die Anzahl der Ziffern steht. Die zeitliche Komplexität von Radix Sort wird also zu O (d * (n + b)) .

Die Raumkomplexität ist O (n + b), da wir hier eine Variation von Counting Sort als Unterprogramm verwendet haben.

7. Fazit

In diesem Artikel haben wir den Radix-Sortieralgorithmus beschrieben und veranschaulicht, wie er implementiert wird.

Wie üblich sind die Code-Implementierungen auf Github verfügbar.