Der Radix Sort-Algorithmus sortiert Zahlensysteme anhand ihrer Stellen. Der Radix Sort wird daher auch Base Sort genannt. Dies bedeutet, dass je Stelle ein eigenes Sortierverfahren (zumeist Counting Sort weil Wertebereich \u00fcberschaubar) eingesetzt wird. Man w\u00fcrde also bei 3 Stellen auch 3x sortieren.<\/p>\n\n\n\n
Es gibt einen Most- und Least-Significant-Radix-Sort (MSD \/ LSD Radix Sort). LSD beginnt bei der niedrigsten Stelle (z.B. den Einern) und bewegt sich zu den h\u00f6heren Stellen (z.B. Zehner, Hunderter). Bei MSD Radix Sort ist das umgekehrt.<\/p>\n\n\n\n
Eine wichtige Voraussetzung ist, das man die gleiche Anzahl an Stellen hat (also z.B. 2 (Tupel), 3 (Tripel) oder mehr Stellen). Weiterhin m\u00fcssen die vorhandenen Elemente in dem Zahlensystem (z.B. Dezimal 0-9) in einer Reihenfolge nach Rang sortierbar sein. D.h. es sollte z.B. klar sein dass ein A vor einem B ist (z.B. durch ASCII-Werte).<\/p>\n\n\n\n
Nehmen wir an, wir m\u00f6chten die Zahlen [170, 45, 75, 90, 802, 24, 2, 66] sortieren:<\/p>\n\n\n\n
Der folgende Code hat die vergangenen Implementierungen von QuickSort und Counting Sort (ohne Stellensortierung durch Radix \/ Base Sort) mit einer Zeitmessung in Echtzeit verglichen und muss angepasst werden. Das nachfolgende Beispiel sortiert Dezimalzahlen (also ein Zahlensystem zur Basis 10).<\/p>\n\n\n
\npackage AlgoDat;\n\nimport java.util.Arrays;\n\npublic class RadixSort {\n \/\/ Zu sortierendes Array\n private static int myArrayRadixSort[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};\n \n public boolean verbose = false;\n\n \/\/ H\u00e4lt die Klassen als instanziertes Objekt\n @SuppressWarnings("unused")\n private static RadixSort programRadixSort;\n @SuppressWarnings("unused")\n private static HelperUtil helper;\n\n \/\/ Hilfsfunktion f\u00fcr das Ausgeben des Arrays\n public void OutputOfIntArray(int myArray[])\n {\n if (myArray != null)\n {\n for (int i = 0; i < myArray.length; i++) {\n if (i > 0) System.out.print(";");\n System.out.print(myArray[i]);\n }\n\n System.out.println();\n }\n }\n\n public void radixSort(int[] arr) \n { \n int max = Arrays.stream(arr).max().getAsInt();\n if (verbose) System.out.println("Gr\u00f6\u00dfte Zahl im Array: " + max);\n \n \/\/ Bei Dezimalzahlen muss die Basis 10 genommen werden\n \/\/ ... bei Gro\u00dfbuchstaben z.B. die Basis 27\n for (int exp = 1; max \/ exp > 0; exp *= 10) \n { \n if (verbose) System.out.println("Suche " + exp + "er.");\n countingSort(arr, exp); \n } \n } \n \n public void countingSort(int[] arr, int exp) \n { \n int n = arr.length; \n int[] output = new int[n]; \n int[] count = new int[10]; \n \n \/\/ Alle 10 Elemente mit 0 initialisieren\n for (int i = 0; i < 10; i++) \n { \n count[i] = 0; \n } \n \n \/\/ Histogramm erstellen\n for (int i = 0; i < n; i++) \n { \n count[(arr[i] \/ exp) % 10]++; \n } \n \n \/\/ Kummuliere, so dass die Anfangspositionen in dem Array stehen\n for (int i = 1; i < 10; i++) \n { \n count[i] += count[i - 1]; \n } \n \n \/\/ Ausgabearray erstellen\n for (int i = n - 1; i >= 0; i--) \n { \n output[count[(arr[i] \/ exp) % 10] - 1] = arr[i]; \n count[(arr[i] \/ exp) % 10]--; \n } \n \n \/\/ Kopiere das neu erstellte Array auf das zu \u00e4ndernde Array\n for (int i = 0; i < n; i++) \n { \n arr[i] = output[i]; \n } \n } \n \n \/\/ Konstruktor\n public RadixSort(int[] toSort)\n {\n this.radixSort(toSort);\n }\n\n \/\/ Konstruktor\n public RadixSort()\n {\n System.out.print("Vorher: ");\n this.OutputOfIntArray(myArray);\n\n this.radixSort(myArray); \n \n System.out.print("Nachher: ");\n this.OutputOfIntArray(myArray);\n }\n\n public static void main(String[] args) \n {\n helper = new HelperUtil();\n\n \/\/ Es gibt 80 Mio Menschen in Deutschland, von denen keiner \u00e4lter als 120 ist -> Kleiner Wertebereich\n int[] alterDerMenschenInDeutschlandRS = helper.generateIntegerArrayOfSize(80000000, 120);\n int[] alterDerMenschenInDeutschlandQS = alterDerMenschenInDeutschlandRS.clone();\n int[] alterDerMenschenInDeutschlandCS = alterDerMenschenInDeutschlandRS.clone();\n \/\/ Erwartung: Da Counting Sort eine lineare Laufzeit hat sollte er bei kleinem Wertebereich am Besten performen\n \n System.out.println("\\nEs gibt 80 Mio Menschen in Deutschland, von denen keiner \u00e4lter als 120 ist -> Kleiner Wertebereich");\n System.out.println("===================================================================");\n \n long startZeitRS = System.nanoTime();\n programRadixSort = new RadixSort(alterDerMenschenInDeutschlandRS);\n long endZeitRS = System.nanoTime();\n System.out.println((endZeitRS-startZeitRS) + " ns (Radix Sort)");\n }\n}\n<\/pre><\/div>\n\n\nAusgabe<\/h2>\n\n\n\nEs gibt 80 Mio Menschen in Deutschland, von denen \nkeiner \u00e4lter als 120 ist -> Kleiner Wertebereich\n=======================================================\n347584000 ns (Counting Sort)\n2544168000 ns (Radix Sort)\n3335958900 ns (Quick Sort)\n<\/pre><\/div>\n\n\nKomplexit\u00e4t: O-Notation (Ordnung)<\/h2>\n\n\n\n
O(n*l) <\/strong>(l=L\u00e4nge also bei ABC = L\u00e4nge: 3 – Anzahl der max. Stellen0)
\u2023 Sortieren von Strings \u00fcber einem endlichen Alphabet durch
mehrmaliges Anwenden von Counting Sort.
\u2023 Angenommen: Alle W\u00f6rter haben die L\u00e4nge
\u2023 Z.b. Postleitzahlen<\/p>\n\n\n\nLaufzeit von Radix Sort: \ud835\udcaa(n), weil l \u22c5 n Durchl\u00e4ufe<\/p>\n