{"id":4830,"date":"2024-09-02T16:00:39","date_gmt":"2024-09-02T16:00:39","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4830"},"modified":"2026-02-17T11:58:57","modified_gmt":"2026-02-17T11:58:57","slug":"radix-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/radix-sort\/","title":{"rendered":"Radix sort &#8211; Sortieren nach numerischen Ordnungen in Java"},"content":{"rendered":"<p>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\u00fcr die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten erfordern. Es gibt eine Vielzahl unterschiedlicher Sortieralgorithmen. Die Wahl des richtigen Algorithmus h\u00e4ngt von Faktoren wie der Gr\u00f6\u00dfe und den Eigenschaften der Eingabedaten, dem verf\u00fcgbaren Speicher sowie den Anforderungen an Zeit- und Speicherkomplexit\u00e4t ab. Um dir die Auswahl zu erleichtern, stellen wir in unserer Serie nach und nach die bekanntesten Sortieralgorithmen vor, erkl\u00e4ren ihre Funktionsweise, Vor- und Nachteile und programmieren sie in Java. Heute besch\u00e4ftigen wir uns mit dem <strong>Radix Sort<\/strong>, einem Algorithmus, der auf der Sortierung nach Stellenwerten basiert. Bisher haben wir die folgenden Sortieralgorithmen behandelt:<\/p>\n<ul>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\" target=\"_blank\" rel=\"noopener\">Sortieralgorithmen<\/a>: eine Einf\u00fchrung in das Sortieren von Daten,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bubble-sort\/\" target=\"_blank\" rel=\"noopener\">Bubble sort<\/a> &#8211; Blasen-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/comb-sort\/\" target=\"_blank\" rel=\"noopener\">Comb sort<\/a> &#8211; Kamm-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/big-o-notation\/\" target=\"_blank\" rel=\"noopener\">Big O Notation<\/a>: Analyse der Komplexit\u00e4t von Algorithmen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\" target=\"_blank\" rel=\"noopener\">Selection sort<\/a> &#8211; Sortieren nach Auswahl,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/insertion-sort\/\" target=\"_blank\" rel=\"noopener\">Insertion sort<\/a> &#8211; Sortieren nach Einf\u00fcgung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/counting-sort\/\" target=\"_blank\" rel=\"noopener\">Counting sort<\/a> &#8211; Sortieren durch Z\u00e4hlen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/heap-sort\/\" target=\"_blank\" rel=\"noopener\">Heap sort<\/a> &#8211; Heap Sortierung<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/merge-sort\/\" target=\"_blank\" rel=\"noopener\">Merge sort<\/a> &#8211; Sortieren durch Aufteilen und Zusammenf\u00fchren,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/quick-sort\/\" target=\"_blank\" rel=\"noopener\">Quick sort <\/a> &#8211; schnelles Sortieren mit Pivot,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bucket-sort\/\" target=\"_blank\" rel=\"noopener\">Bucket Sort <\/a> (Bin Sort) \u2013 Sortieren mit Eimern (Bins)<\/li>\n<\/ul>\n<h2>Radix sort Algorithmus<\/h2>\n<p>Radix Sort ist ein effizienter Sortieralgorithmus f\u00fcr Zahlen oder Zeichenketten mit Schl\u00fcsseln fester L\u00e4nge. Er geh\u00f6rt 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<strong>(LSD<\/strong> ) oder vom Anfang, d.h. von der h\u00f6chstwertigen Ziffer<strong>(MSD<\/strong> ) beginnen. Die Sortierung verwendet einen modifizierten<a href=\"https:\/\/msgprogramator.sk\/de\/counting-sort\/\" target=\"_blank\" rel=\"noopener\">Z\u00e4hlsortieralgorithmus<\/a>, den wir bereits vorgestellt haben. Die Zahlen werden immer nach einer Reihenfolge sortiert und erst dann wird zum n\u00e4chsten Schritt \u00fcbergegangen, wobei die Reihenfolge aus dem vorherigen Schritt ber\u00fccksichtigt wird. Obwohl die Geschichte des Algorithmus bis ins Jahr 1887 zur\u00fcckreicht und er Anfang des 20. Jahrhunderts zum Sortieren von Lochkarten verwendet wurde, wird er auch heute noch in der <strong>bin\u00e4ren MSD-Radixsortierung<\/strong> eingesetzt und ebenso in Kombination mit anderen Algorithmen in so genannten hybriden Algorithmen verwendet.<\/p>\n<h2>Radix Sort \u2013 Funktionsprinzip des Algorithmus<\/h2>\n<p>In unserem Beispiel nehmen wir LSD. Diese Form der Radix-Sortierung hat gegen\u00fcber MSD den Vorteil, dass der Sortieralgorithmus stabil ist. Bevor die eigentliche Sortierung beginnt, m\u00fcssen wir herausfinden, wie hoch die maximale Zahl im unsortierten Eingabefeld ist. Die Anzahl seiner Ziffern bestimmt dann die Anzahl der Durchl\u00e4ufe, die erforderlich sind, um die Eingabe vollst\u00e4ndig zu sortieren. Anhand unseres Beispiels in der Abbildung k\u00f6nnen wir sehen, dass die maximale Zahl 958 und die Anzahl der \u00dcberg\u00e4nge 3 betr\u00e4gt. Als n\u00e4chstes w\u00e4hlen wir bereits die Art der Radix-Sortierung (MSD oder LSD). Wir \u00fcbergeben nacheinander Ziffern anstelle von Einern, Zehnern, Hundertern usw. Mithilfe der z\u00e4hlenden 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 \u00dcbergangs zu erhalten.<\/p>\n<p>Zum Beispiel. nach dem Sortieren der Zahlen anstelle der Einheiten (blaue Tabelle), k\u00f6nnen wir feststellen, dass die Zahlen sortiert sind und gleichzeitig dieselben Zahlen ihre relative Reihenfolge im Vergleich zur Eingabe beibehalten (Stabilit\u00e4t des Algorithmus). Die gr\u00fcne Tabelle zeigt den Zustand nach der Sortierung nach dem Zehnerradix und die orange Tabelle zeigt bereits das endg\u00fcltige Sortierergebnis nach der Sortierung nach dem Hunderterradix. In unserem Beispiel waren alle Zahlen dreistellig. H\u00e4tten wir jedoch zweistellige oder einstellige Einsen unter ihnen, m\u00fcssten wir sie so behandeln, als ob ihr numerisches Pr\u00e4fix mit Nullen gef\u00fcllt w\u00e4re.<\/p>\n<h2>Radix sort &#8211; Animation, Visualisierung<\/h2>\n<figure id=\"attachment_4240\" aria-describedby=\"caption-attachment-4240\" style=\"width: 900px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4238 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/vizualne-znazornenie-algoritmu-radix-sort-900-500.webp\" alt=\"Visuelle Darstellung des Radix-Sort (LSD) Algorithmus. Die numerischen Reihenfolgen werden zuerst sortiert: Einsen, Zehner und schlie\u00dflich Hunderter. \" width=\"900\" height=\"500\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/vizualne-znazornenie-algoritmu-radix-sort-900-500.webp 900w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/vizualne-znazornenie-algoritmu-radix-sort-900-500-300x167.webp 300w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/vizualne-znazornenie-algoritmu-radix-sort-900-500-768x427.webp 768w\" sizes=\"auto, (max-width: 900px) 100vw, 900px\" \/><figcaption id=\"caption-attachment-4240\" class=\"wp-caption-text\">Visuelle Darstellung des Radix Sort (LSD) Algorithmus. Die numerischen Reihenfolgen werden zuerst sortiert: Einsen, Zehner und schlie\u00dflich Hunderter.<\/figcaption><\/figure>\n<h2>Vorteile des Radix Sort Algorithmus<\/h2>\n<ul>\n<li>Schnell, wenn die Tasten kurz sind und aus einem relativ schmalen Band stammen.<\/li>\n<li>Auch geeignet zum Sortieren von Zeichen in Zeichenketten (string).<\/li>\n<li>Die LSD-Form ist immer stabil, MSD kann an einen stabilen Algorithmus angepasst werden.<\/li>\n<li>Es kann parallelisiert werden, um die Berechnungslast auf mehrere Prozessoren zu verteilen.<\/li>\n<\/ul>\n<h2>Nachteile des Radix sort Algorithmus<\/h2>\n<ul>\n<li>Ben\u00f6tigt zus\u00e4tzlichen Speicherplatz.<\/li>\n<li>Es ist nicht sehr flexibel, sondern muss f\u00fcr verschiedene Datentypen angepasst werden.<\/li>\n<\/ul>\n<h2>Radix Sort \u2013 Zeitkomplexit\u00e4t<\/h2>\n<table width=\"536\">\n<thead>\n<tr>\n<th rowspan=\"2\" width=\"94\"><strong>Algorithmus<\/strong><\/th>\n<th rowspan=\"2\" width=\"84\"><strong>Methode<\/strong><\/th>\n<th colspan=\"3\" width=\"208\"><strong>Zeitliche Komplexit\u00e4t<\/strong><\/th>\n<th rowspan=\"2\" width=\"82\"><strong>Speicher<\/strong><\/th>\n<th rowspan=\"2\" width=\"69\"><strong>Stabil<\/strong><\/th>\n<\/tr>\n<tr>\n<th width=\"73\"><strong>schlechteste<\/strong><\/th>\n<th width=\"63\"><strong>durchschnittlich<\/strong><\/th>\n<th width=\"71\"><strong>beste<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td width=\"94\">Radix sort<\/td>\n<td width=\"84\">Z\u00e4hlen, Verteilung<\/td>\n<td width=\"73\">O(n * k)<\/td>\n<td width=\"63\">O(n * k)<\/td>\n<td width=\"71\">O(n + k)<\/td>\n<td width=\"82\">O(n + k)<\/td>\n<td width=\"69\">Ja<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Auf dieser <a href=\"https:\/\/www.hackerearth.com\/practice\/algorithms\/sorting\/radix-sort\/visualize\/\" target=\"_blank\" rel=\"nofollow noopener\">Seite <\/a> kannst du die einzelnen Schritte des Algorithmus durchgehen, wodurch du die Zeitkomplexit\u00e4t des Algorithmus \u00fcberpr\u00fcfen kannst.<\/p>\n<h2>Radix Sort &#8211; Implementierung, Java-Code<\/h2>\n<p>Wir werden nun eine Implementierung des Radix sort Algorithmus (LSD-Version) in Java zeigen.<\/p>\n<p><strong><u>RadixSort.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">package sorting;\n\npublic class RadixSort {\n    private final int BASE = 10; \/\/ digits [0-9]\n\n    int getMaxElement(int[] data) {\n        int max = data[0];\n        for (int i = 1; i &lt; data.length; i++)\n            if (data[i] &gt; max)\n                max = data[i];\n        return max;\n    }\n\n    public void sort(int[] data)\n    {\n        \/\/ Get maximum element\n        int max = getMaxElement(data);\n        \/\/ Apply counting sort to sort elements based on radix value\n        for (int radix = 1; max \/ radix &gt; 0; radix *= BASE)\n            radixCountingSort(data, radix);\n    }\n\n    void radixCountingSort(int[] data, int radix) {\n        int[] output = new int[data.length + 1];\n        int[] count = new int[BASE];\n        \/\/ Calculate count of elements\n        for (int i = 0; i &lt; data.length; i++)\n            count[(data[i] \/ radix) % BASE]++;\n        \/\/ Calculate cumulative count\n        for (int i = 1; i &lt; BASE; i++)\n            count[i] += count[i - 1];\n        \/\/ Place the elements in sorted radix order\n        for (int i = data.length - 1; i &gt;= 0; i--) {\n            output[count[(data[i] \/ radix) % BASE] - 1] = data[i];\n            count[(data[i] \/ radix) % BASE]--;\n        }\n        \/\/ Copy array from output back to data\n        System.arraycopy(output, 0, data, 0, data.length);\n        System.out.print(&quot;Radix: &quot; + radix + &quot; -&gt; &quot;);\n        printArray(data);\n    }\n\n    \/\/ Function to print an array\n    public void printArray(int[] data)\n    {\n        for (int i = 0; i &lt; data.length; i++)\n            System.out.print(data[i] + &quot; &quot;);\n        System.out.println();\n    }\n}<\/code><\/pre>\n<p><strong><u>Main.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">import sorting.RadixSort;\n\npublic class Main {\n    public static void main(String[] args) {\n        int[] dataToSort = { 165, 958, 635, 694, 480, 637, 5, 598, 82};\n        RadixSort radixSort = new RadixSort();\n        System.out.print(&quot;Input: &quot;);\n        radixSort.printArray(dataToSort);\n        radixSort.sort(dataToSort);\n        System.out.print(&quot;Sorted: &quot;);\n        radixSort.printArray(dataToSort);\n    }\n}<\/code><\/pre>\n<p>Die Ausgabe dieses Beispiels ist:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4241 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/vystup-z-prikladu-radix-sort-530-245.webp\" alt=\"Radix Sort - Implementierung, Java-Code - Ausgabe des Beispiels\" width=\"530\" height=\"245\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/vystup-z-prikladu-radix-sort-530-245.webp 530w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/vystup-z-prikladu-radix-sort-530-245-300x139.webp 300w\" sizes=\"auto, (max-width: 530px) 100vw, 530px\" \/><\/p>\n<p>Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausf\u00fchren kannst. Lade den <a href=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/09\/RadixSort.zip\" target=\"_blank\" rel=\"noopener\"><strong>RadixSort<\/strong> Java-Code<\/a> herunter.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel erf\u00e4hrst du, was Radix Sort ist, wie er funktioniert, welche Vor- und Nachteile er hat, siehst eine Visualisierung und ein Beispiel in Java-Code.<\/p>\n","protected":false},"author":14,"featured_media":5313,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[57],"tags":[],"class_list":["post-4830","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4830","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/comments?post=4830"}],"version-history":[{"count":4,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4830\/revisions"}],"predecessor-version":[{"id":9746,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4830\/revisions\/9746"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media\/5313"}],"wp:attachment":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media?parent=4830"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/categories?post=4830"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/tags?post=4830"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}