Fangen wir mit der letzten Frage an:<\/p>\n\n\n\n
Was ist Radix Sort?<\/h2>\n\n\n\n
\"Radix\" ist zwar das lateinische Wort f\u00fcr \"Wurzel\" \u2013 dennoch hat Radix Sort nichts mit Wurzelziehen zu tun.<\/p>\n\n\n\n
Die \"Radix\" eines Zahlensystems (auch \"Basis\" genannt) bezeichnet vielmehr die Anzahl der Ziffern, die zur Darstellung von Zahlen in diesem Zahlensystem ben\u00f6tigt werden. Die Radix im Dezimalsystem ist 10, die Radix des Bin\u00e4rsystems ist 2, und die Radix des Hexadezimalsystems ist 16.<\/p>\n\n\n\n
Bei Radix Sort sortieren wir die Zahlen Ziffer f\u00fcr Ziffer<\/em> \u2013 und nicht, wie bei den meisten anderen Sortierverfahren, indem wir zwei Zahlen<\/em> miteinander vergleichen. Wie genau das funktioniert, liest du im folgenden Kapitel.<\/p>\n\n\n\n Den Algorithmus f\u00fcr Radix Sort erkl\u00e4re ich am besten Schritt f\u00fcr Schritt an einem Beispiel. Folgende Zahlen sollen sortiert werden:<\/p>\n\n\n Wir betrachten zu Beginn ausschlie\u00dflich die letzte<\/em> Ziffer (es gibt auch Radix-Sort-Varianten, bei denen man bei der ersten<\/em> Ziffer beginnt, aber dazu kommen wir sp\u00e4ter):<\/p>\n\n\n Wir sortieren die Zahlen in zwei Phasen: einer Partitionierungsphase und einer Sammelphase.<\/p>\n\n\n\n F\u00fcr die Partitionierung legen wir zehn sogenannte \"Buckets\" an, bezeichnet mit \"0\" bis \"9\". Auf diese verteilen wir die Zahlen entsprechend ihrer jeweils letzten Ziffer. Die folgende Grafik demonstriert, wie wir die erste Zahl, die 41, in den Bucket \"1\" legen:<\/p>\n\n\n Die zweite Zahl, die 573, legen wir, entsprechend ihrer letzten Ziffer, in den Bucket \"3\":<\/p>\n\n\n Die dritte Zahl, die 3, legen wir ebenfalls in den Bucket \"3\":<\/p>\n\n\n Auf die gleiche Art verteilen wir auch die restlichen Zahlen auf die Buckets:<\/p>\n\n\n Die Partitionierungsphase f\u00fcr die letzte Ziffer ist damit abgeschlossen.<\/p>\n\n\n\n An die Partitionierungsphase schlie\u00dft sich die Sammelphase an. Wir sammeln die Zahlen, Bucket f\u00fcr Bucket, in aufsteigender Reihenfolge \u2013 und innerhalb der Buckets von links nach rechts (also in der gleichen Reihenfolge wie die Zahlen in den jeweiligen Bucket eingetragen wurden) \u2013 in eine neue Liste.<\/p>\n\n\n\n Wir beginnen mit dem Buckets mit der kleinsten Ziffer, also Bucket 1:<\/p>\n\n\n Danach sammeln wir die Zahlen des n\u00e4chsth\u00f6heren Buckets, also Bucket 3:<\/p>\n\n\n Und schlie\u00dflich die Zahlen aus Bucket 6 und dann Bucket 8:<\/p>\n\n\n Alle Buckets sind nun geleert:<\/p>\n\n\n In dieser neuen Liste sind die Zahlen nach ihrer letzten Ziffer aufsteigend sortiert: 1, 1, 3, 3, 3, 6, 8<\/p>\n\n\n\n Wir wiederholen die Partitionierungs- und Sammelphase f\u00fcr die Zehnerstelle. Die zwei Phasen stelle ich dieses Mal mit nur jeweils einer Grafik dar.<\/p>\n\n\n\n In der Partitionierungsphase verteilen wir die Zahlen nach ihrer Zehnerstelle auf die Buckets:<\/p>\n\n\n Die Zehnerstelle von einstelligen<\/em> Zahlen ist die Null. Dementsprechend habe ich die Drei als \"03\" dargestellt.<\/p>\n\n\n\n In der Sammelphase entnehmen wir die Zahlen wieder Bucket f\u00fcr Bucket:<\/p>\n\n\n Die Zahlen sind nun nach ihren jeweils zwei<\/em> letzten Ziffern sortiert: 3, 8, 36, 41, 71, 73, 93<\/p>\n\n\n\n Die gleiche Prozedur wiederholen wir f\u00fcr die Hunderterstelle. Zun\u00e4chst die Partitionierungsphase:<\/p>\n\n\n Und im Anschluss die Sammelphase:<\/p>\n\n\n Nach der dritten und letzten Sammelphase sind die Zahlen nun vollst\u00e4ndig sortiert.<\/p>\n\n\n\n Hier noch einmal das Endergebnis ohne f\u00fchrende Nullen:<\/p>\n\n\nRadix Sort Algorithmus<\/h2>\n\n\n\n
![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-numbers-to-sort-600x39.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-highlighted-600x39.png\")
<\/figure>\n<\/div>\n\n\nPartitionierungsphase<\/h3>\n\n\n\n
![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-partitioning-step1-600x416.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-partitioning-step2.v2-600x417.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-partitioning-step3.v2-600x416.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-partitioning-step4-7.v2-600x416.png\")
<\/figure>\n<\/div>\n\n\nSammelphase<\/h3>\n\n\n\n
![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-collection-bucket-1-600x416.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-collection-bucket-3.v2-600x416.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-collection-bucket-6-8.v2-600x416.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-last-digit-collection-done-600x416.png\")
<\/figure>\n<\/div>\n\n\nNach Zehnerstelle sortieren<\/h3>\n\n\n\n
![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-middle-digit-partitioning-600x417.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-middle-digit-collection-600x416.png\")
<\/figure>\n<\/div>\n\n\nNach Hunderterstelle sortieren<\/h3>\n\n\n\n
![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-first-digit-partitioning-600x424.png\")
<\/figure>\n<\/div>\n\n\n![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-first-digit-collection-600x416.png\")
<\/figure>\n<\/div>\n\n\n
![\"Radix](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/radix-sort-all-numbers-sorted-600x38.png\")
<\/figure>\n<\/div>\n\n\n