Java Entwickler Experte
Radix sort – Sortieren nach numerischen Ordnungen in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste entweder aufsteigend oder absteigend nach numerischer oder lexikografischer Reihenfolge anzuordnen. Das Sortieren ist entscheidend für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten erfordern. Es gibt eine Vielzahl unterschiedlicher Sortieralgorithmen. Die Wahl des richtigen Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher sowie den Anforderungen an Zeit- und Speicherkomplexität ab. Um dir die Auswahl zu erleichtern, stellen wir in unserer Serie nach und nach die bekanntesten Sortieralgorithmen vor, erklären ihre Funktionsweise, Vor- und Nachteile und programmieren sie in Java. Heute beschäftigen wir uns mit dem Radix Sort, einem Algorithmus, der auf der Sortierung nach Stellenwerten basiert. Bisher haben wir die folgenden Sortieralgorithmen behandelt:
In diesem Artikel erfährst du:
- Sortieralgorithmen: eine Einführung in das Sortieren von Daten,
- Bubble sort – Blasen-Sortierung,
- Comb sort – Kamm-Sortierung,
- Big O Notation: Analyse der Komplexität von Algorithmen,
- Selection sort – Sortieren nach Auswahl,
- Insertion sort – Sortieren nach Einfügung,
- Counting sort – Sortieren durch Zählen,
- Heap sort – Heap Sortierung
- Merge sort – Sortieren durch Aufteilen und Zusammenführen,
- Quick sort – schnelles Sortieren mit Pivot,
- Bucket Sort (Bin Sort) – Sortieren mit Eimern (Bins)
Radix sort Algorithmus
Radix Sort ist ein effizienter Sortieralgorithmus für Zahlen oder Zeichenketten mit Schlüsseln fester Länge. Er gehört zu den Algorithmen, die nicht nach dem Vergleichsprinzip arbeiten. Wie das Wort Radix (d.h. numerische Ordnung) schon sagt, erfolgt die Sortierung durch sukzessive Verarbeitung und Sortierung nach einzelnen Ziffern oder Zeichen. Die Sortierung kann vom Ende der Zeichenkette, d.h. von der niedrigstwertigen Ziffer(LSD ) oder vom Anfang, d.h. von der höchstwertigen Ziffer(MSD ) beginnen. Die Sortierung verwendet einen modifiziertenZählsortieralgorithmus, den wir bereits vorgestellt haben. Die Zahlen werden immer nach einer Reihenfolge sortiert und erst dann wird zum nächsten Schritt übergegangen, wobei die Reihenfolge aus dem vorherigen Schritt berücksichtigt wird. Obwohl die Geschichte des Algorithmus bis ins Jahr 1887 zurückreicht und er Anfang des 20. Jahrhunderts zum Sortieren von Lochkarten verwendet wurde, wird er auch heute noch in der binären MSD-Radixsortierung eingesetzt und ebenso in Kombination mit anderen Algorithmen in so genannten hybriden Algorithmen verwendet.
Radix Sort – Funktionsprinzip des Algorithmus
In unserem Beispiel nehmen wir LSD. Diese Form der Radix-Sortierung hat gegenüber MSD den Vorteil, dass der Sortieralgorithmus stabil ist. Bevor die eigentliche Sortierung beginnt, müssen wir herausfinden, wie hoch die maximale Zahl im unsortierten Eingabefeld ist. Die Anzahl seiner Ziffern bestimmt dann die Anzahl der Durchläufe, die erforderlich sind, um die Eingabe vollständig zu sortieren. Anhand unseres Beispiels in der Abbildung können wir sehen, dass die maximale Zahl 958 und die Anzahl der Übergänge 3 beträgt. Als nächstes wählen wir bereits die Art der Radix-Sortierung (MSD oder LSD). Wir übergeben nacheinander Ziffern anstelle von Einern, Zehnern, Hundertern usw. Mithilfe der zählenden Sortierung finden wir die Vielfachheit jeder Ziffer, ihre Indizes im sortierten Ergebnis und verwenden diese dann, um die Zahlen in der Eingabe neu anzuordnen, um die sortierten Zahlen auf der Grundlage des aktuellen Übergangs zu erhalten.
Zum Beispiel. nach dem Sortieren der Zahlen anstelle der Einheiten (blaue Tabelle), können wir feststellen, dass die Zahlen sortiert sind und gleichzeitig dieselben Zahlen ihre relative Reihenfolge im Vergleich zur Eingabe beibehalten (Stabilität des Algorithmus). Die grüne Tabelle zeigt den Zustand nach der Sortierung nach dem Zehnerradix und die orange Tabelle zeigt bereits das endgültige Sortierergebnis nach der Sortierung nach dem Hunderterradix. In unserem Beispiel waren alle Zahlen dreistellig. Hätten wir jedoch zweistellige oder einstellige Einsen unter ihnen, müssten wir sie so behandeln, als ob ihr numerisches Präfix mit Nullen gefüllt wäre.
Radix sort – Animation, Visualisierung
Vorteile des Radix Sort Algorithmus
- Schnell, wenn die Tasten kurz sind und aus einem relativ schmalen Band stammen.
- Auch geeignet zum Sortieren von Zeichen in Zeichenketten (string).
- Die LSD-Form ist immer stabil, MSD kann an einen stabilen Algorithmus angepasst werden.
- Es kann parallelisiert werden, um die Berechnungslast auf mehrere Prozessoren zu verteilen.
Nachteile des Radix sort Algorithmus
- Benötigt zusätzlichen Speicherplatz.
- Es ist nicht sehr flexibel, sondern muss für verschiedene Datentypen angepasst werden.
Radix Sort – Zeitkomplexität
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Radix sort | Zählen, Verteilung | O(n * k) | O(n * k) | O(n + k) | O(n + k) | Ja |
Auf dieser Seite kannst du die einzelnen Schritte des Algorithmus durchgehen, wodurch du die Zeitkomplexität des Algorithmus überprüfen kannst.
Radix Sort – Implementierung, Java-Code
Wir werden nun eine Implementierung des Radix sort Algorithmus (LSD-Version) in Java zeigen.
RadixSort.java
package sorting;
public class RadixSort {
private final int BASE = 10; // digits [0-9]
int getMaxElement(int[] data) {
int max = data[0];
for (int i = 1; i < data.length; i++)
if (data[i] > max)
max = data[i];
return max;
}
public void sort(int[] data)
{
// Get maximum element
int max = getMaxElement(data);
// Apply counting sort to sort elements based on radix value
for (int radix = 1; max / radix > 0; radix *= BASE)
radixCountingSort(data, radix);
}
void radixCountingSort(int[] data, int radix) {
int[] output = new int[data.length + 1];
int[] count = new int[BASE];
// Calculate count of elements
for (int i = 0; i < data.length; i++)
count[(data[i] / radix) % BASE]++;
// Calculate cumulative count
for (int i = 1; i < BASE; i++)
count[i] += count[i - 1];
// Place the elements in sorted radix order
for (int i = data.length - 1; i >= 0; i--) {
output[count[(data[i] / radix) % BASE] - 1] = data[i];
count[(data[i] / radix) % BASE]--;
}
// Copy array from output back to data
System.arraycopy(output, 0, data, 0, data.length);
System.out.print("Radix: " + radix + " -> ");
printArray(data);
}
// Function to print an array
public void printArray(int[] data)
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}Main.java
import sorting.RadixSort;
public class Main {
public static void main(String[] args) {
int[] dataToSort = { 165, 958, 635, 694, 480, 637, 5, 598, 82};
RadixSort radixSort = new RadixSort();
System.out.print("Input: ");
radixSort.printArray(dataToSort);
radixSort.sort(dataToSort);
System.out.print("Sorted: ");
radixSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Lade den RadixSort Java-Code herunter.
