{"id":12217,"date":"2020-09-02T09:00:40","date_gmt":"2020-09-02T07:00:40","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=12217"},"modified":"2025-06-12T09:25:02","modified_gmt":"2025-06-12T07:25:02","slug":"counting-sort","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/counting-sort\/","title":{"rendered":"Counting Sort \u2013 Algorithmus, Quellcode, Zeitkomplexit\u00e4t"},"content":{"rendered":"\n<p>Alle bisher in dieser <a href=\"\/de\/algorithmen\/sortieralgorithmen\/\">Artikelserie<\/a> behandelten Sortierverfahren basieren auf dem Vergleich, ob zwei Zahlen <em>kleiner<\/em>, <em>gr\u00f6\u00dfer<\/em> oder <em>gleich<\/em> sind. Counting Sort basiert auf einer komplett anderen, nicht-vergleichsbasierten Herangehensweise.<\/p>\n\n\n\n<p>Dieser Artikel beantwortet folgende Fragen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wie funktioniert Counting Sort?<\/li>\n\n\n\n<li>Was unterscheiden sich die vereinfachte Form von Counting Sort und die allgemeine Form?<\/li>\n\n\n\n<li>Wie sieht der Quellcode von Counting Sort aus?<\/li>\n\n\n\n<li>Wie bestimmt man die Zeitkomplexit\u00e4t von Counting Sort?<\/li>\n\n\n\n<li>Warum ist Counting Sort trotz exakt gleicher Anzahl an Operationen f\u00fcr vorsortierte Zahlenfolgen fast zehn Mal schneller als f\u00fcr unsortierte?<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-algorithmus-vereinfachte-form\">Counting Sort Algorithmus (Vereinfachte Form)<\/h2>\n\n\n\n<p>Anstatt Elemente zu vergleichen, wird bei Counting Sort gez\u00e4hlt, wie oft welche Elemente in der zu sortierenden Menge vorkommen.<\/p>\n\n\n\n<p>Eine vereinfachte Form von Counting Sort kann angewendet werden, wenn Zahlen (z. B. <code>int<\/code>-Primitive) sortiert werden sollen \u2013 f\u00fcr Objekte, die entsprechend ihrer Keys sortiert werden sollen, wirst du im Anschluss die <em>allgemeine<\/em> Form von Counting Sort kennenlernen.<\/p>\n\n\n\n<p>Die vereinfachte Form besteht aus zwei Phasen:<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-algorithmus-phase-1-elemente-zaehlen\">Counting Sort Algorithmus \u2013 Phase 1: Elemente z\u00e4hlen<\/h3>\n\n\n\n<p>Zun\u00e4chst wird ein zus\u00e4tzliches Array angelegt, dessen L\u00e4nge der Gr\u00f6\u00dfe des Zahlenraums entspricht (z. B. ein Array der Gr\u00f6\u00dfe 256, um Bytes zu sortieren). Dann iteriert man einmal \u00fcber die zu sortierenden Elemente und erh\u00f6ht f\u00fcr jedes Element den Wert im Array an derjenigen Position, die der zu sortierenden Zahl entspricht, um eins.<\/p>\n\n\n\n<p>Hier ein Beispiel mit dem Zahlenraum 0\u20139 (d. h. in dem zu sortierenden Array kommen nur Zahlen von 0 bis 9 vor). <\/p>\n\n\n\n<p>Folgendes Array soll sortiert werden:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1346\" height=\"76\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted.png\" alt=\"Counting Sort Algorithmus - zu sortierendes Array\" class=\"wp-image-15766\" style=\"width:673px;height:38px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted.png 1346w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-224x13.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-336x19.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-504x28.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-672x38.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-400x23.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-600x34.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-800x45.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-944x53.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_array_to_be_sorted-1200x68.png 1200w\" sizes=\"(max-width: 1346px) 100vw, 1346px\" \/><\/figure>\n<\/div>\n\n\n<p>Wir erstellen ein zus\u00e4tzliches Array der L\u00e4nge 10, das mit Nullen initialisiert ist. In der Grafik wird unter der Linie der Array-Index mit angezeigt:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"924\" height=\"110\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array.png\" alt=\"Counting Sort Algorithmus - Z\u00e4hler-Array\" class=\"wp-image-15767\" style=\"width:462px;height:55px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array.png 924w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array-224x27.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array-336x40.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array-504x60.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array-672x80.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array-400x48.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array-600x71.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counters_array-800x95.png 800w\" sizes=\"(max-width: 924px) 100vw, 924px\" \/><\/figure>\n<\/div>\n\n\n<p>Nun iterieren wir \u00fcber das zu sortierende Array. Das erste Element ist eine 3 \u2013 dementsprechend erh\u00f6hen wir den Wert im Hilfsarray an der Position 3 um eins:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1352\" height=\"340\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1.png\" alt=\"Counting Sort Algorithmus - Z\u00e4hlen, Schritt 1\" class=\"wp-image-15768\" style=\"width:676px;height:170px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1.png 1352w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-224x56.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-336x84.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-504x127.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-672x169.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-400x101.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-600x151.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-800x201.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-944x237.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_1-1200x302.png 1200w\" sizes=\"(max-width: 1352px) 100vw, 1352px\" \/><\/figure>\n<\/div>\n\n\n<p>Das zweite Element ist eine 7. Wir erh\u00f6hen im Hilfsarray das Feld an Position 7 um eins:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1352\" height=\"340\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2.png\" alt=\"Counting Sort Algorithmus - Z\u00e4hlen, Schritt 2\" class=\"wp-image-15769\" style=\"width:676px;height:170px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2.png 1352w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-224x56.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-336x84.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-504x127.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-672x169.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-400x101.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-600x151.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-800x201.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-944x237.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_step_2-1200x302.png 1200w\" sizes=\"(max-width: 1352px) 100vw, 1352px\" \/><\/figure>\n<\/div>\n\n\n<p>Es folgen die Elementen 4 und 6 \u2013 dementsprechend erh\u00f6hen wir auch die Werte an den Positionen 4 und 6 jeweils um eins:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1352\" height=\"340\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4.png\" alt=\"Counting Sort Algorithmus - Z\u00e4hlen, Schritte 3 und 4\" class=\"wp-image-15770\" style=\"width:676px;height:170px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4.png 1352w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-224x56.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-336x84.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-504x127.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-672x169.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-400x101.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-600x151.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-800x201.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-944x237.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_3_and_4-1200x302.png 1200w\" sizes=\"(max-width: 1352px) 100vw, 1352px\" \/><\/figure>\n<\/div>\n\n\n<p>Mit den n\u00e4chsten zwei Elementen \u2013 der 6 und der 3 \u2013 folgen zwei Elemente, die schon einmal vorkamen. Entsprechend werden die Felder im Hilfsarray von 1 auf 2 erh\u00f6ht:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1346\" height=\"414\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png.png\" alt=\"Counting Sort Algorithmus - Z\u00e4hlen, Schritte 5 und 6\" class=\"wp-image-15771\" style=\"width:673px;height:207px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png.png 1346w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-224x69.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-336x103.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-504x155.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-672x207.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-400x123.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-600x185.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-800x246.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-944x290.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_5_and_6.png-1200x369.png 1200w\" sizes=\"(max-width: 1346px) 100vw, 1346px\" \/><\/figure>\n<\/div>\n\n\n<p>Das Prinzip sollte nun klar sein. Nachdem auch die Hilfsarray-Werte f\u00fcr die restlichen zu sortierenden Elemente entsprechend erh\u00f6ht wurden, sieht das Hilfsarray am Ende wie folgt aus:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1352\" height=\"536\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1.png\" alt=\"Counting Sort Algorithmus - Z\u00e4hlen, Schritte 7 bis 15\" class=\"wp-image-15772\" style=\"width:676px;height:268px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1.png 1352w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-224x89.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-336x133.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-504x200.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-672x266.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-400x159.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-600x238.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-800x317.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-944x374.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_counting_steps_7_to_15-1-1200x476.png 1200w\" sizes=\"(max-width: 1352px) 100vw, 1352px\" \/><\/figure>\n<\/div>\n\n\n<p>Aus diesem sogenannten Histogramm l\u00e4sst sich folgendes ablesen:<\/p>\n\n\n\n<p>Die zu sortierenden Elemente enthalten:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>1 mal die 0,<\/li>\n\n\n\n<li>0 mal die 1,<\/li>\n\n\n\n<li>1 mal die 2,<\/li>\n\n\n\n<li>3 mal die 3,<\/li>\n\n\n\n<li>1 mal die 4,<\/li>\n\n\n\n<li>0 mal die 5,<\/li>\n\n\n\n<li>5 mal die 6,<\/li>\n\n\n\n<li>1 mal die 7,<\/li>\n\n\n\n<li>2 mal die 8 und<\/li>\n\n\n\n<li>1 mal die 9.<\/li>\n<\/ul>\n\n\n\n<p>Diese Informationen werden wir in Phase 2 verwenden, um das zu sortierende Array neu anzuordnen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-algorithmus-phase-2-elemente-neu-anordnen\">Counting Sort Algorithmus \u2013 Phase 2: Elemente neu anordnen<\/h3>\n\n\n\n<p>In Phase zwei iterieren wir einmal \u00fcber das Histogramm-Array. Dabei schreiben wir den jeweiligen Array-Index so oft in das zu sortierende Array, wie es das Histogramm an der entsprechenden Stelle anzeigt.<\/p>\n\n\n\n<p>Im Beispiel starten wir an Position 0 im Hilfsarray. Dort steht die 1, wir schreiben daher die 0 genau <em>ein<\/em> Mal in das zu sortierende Array. <\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1346\" height=\"682\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1.png\" alt=\"Counting Sort Algorithmus - Neu anordnen, Schritt 1\" class=\"wp-image-15774\" style=\"width:673px;height:341px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1.png 1346w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-224x113.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-336x170.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-504x255.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-672x340.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-400x203.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-600x304.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-800x405.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-944x478.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_1-1200x608.png 1200w\" sizes=\"(max-width: 1346px) 100vw, 1346px\" \/><\/figure>\n<\/div>\n\n\n<p>(Die restlichen Zahlen habe ich ausgegraut, da sie zwar nach wie vor im Array stehen, wir sie aber nicht mehr ben\u00f6tigen, da wir diese Informationen jetzt komplett im Histogramm haben.)<\/p>\n\n\n\n<p>An Position 1 im Histogramm steht eine 0, d. h. wir \u00fcberspringen dieses Feld \u2013 es wird <em>keine<\/em> 1 in das zu sortierende Array geschrieben.<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1346\" height=\"682\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2.png\" alt=\"Counting Sort Algorithmus - Neu anordnen, Schritt 2\" class=\"wp-image-15775\" style=\"width:673px;height:341px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2.png 1346w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-224x113.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-336x170.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-504x255.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-672x340.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-400x203.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-600x304.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-800x405.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-944x478.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_2-1200x608.png 1200w\" sizes=\"(max-width: 1346px) 100vw, 1346px\" \/><\/figure>\n<\/div>\n\n\n<p>Position 2 des Histogramms enth\u00e4lt wieder eine 1; wir schreiben also <em>einmal<\/em> eine 2 in das zu sortierende Array:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1346\" height=\"682\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3.png\" alt=\"Counting Sort Algorithmus - Neu anordnen, Schritt 3\" class=\"wp-image-15776\" style=\"width:673px;height:341px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3.png 1346w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-224x113.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-336x170.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-504x255.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-672x340.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-400x203.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-600x304.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-800x405.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-944x478.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_3-1200x608.png 1200w\" sizes=\"(max-width: 1346px) 100vw, 1346px\" \/><\/figure>\n<\/div>\n\n\n<p>Kommen wir zu Position 3, diese enth\u00e4lt eine 3, wir schreiben also <em>drei<\/em> Mal eine 3 in das Array:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1346\" height=\"682\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4.png\" alt=\"Counting Sort Algorithmus - Neu anordnen, Schritt 4\" class=\"wp-image-15778\" style=\"width:673px;height:341px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4.png 1346w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-224x113.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-336x170.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-504x255.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-672x340.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-400x203.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-600x304.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-800x405.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-944x478.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_step_4-1200x608.png 1200w\" sizes=\"(max-width: 1346px) 100vw, 1346px\" \/><\/figure>\n<\/div>\n\n\n<p>Und so geht es weiter... wir schreiben einmal die 4, f\u00fcnfmal die 6, einmal die 7, zweimal die 8 und zuletzt einmal die 9 in das zu sortierende Array:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1346\" height=\"684\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10.png\" alt=\"Counting Sort Algorithmus - Neu anordnen, Schritte 5 bis 10\" class=\"wp-image-15780\" style=\"width:673px;height:342px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10.png 1346w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-224x114.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-336x171.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-504x256.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-672x341.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-400x203.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-600x305.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-800x407.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-944x480.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_algorithm_rearrange_steps_5_to_10-1200x610.png 1200w\" sizes=\"(max-width: 1346px) 100vw, 1346px\" \/><\/figure>\n<\/div>\n\n\n<p>Die Zahlen sind sortiert, der Algorithmus ist beendet.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-java-code-beispiel-vereinfachte-form\">Counting Sort Java Code Beispiel (Vereinfachte Form)<\/h2>\n\n\n\n<p>Im folgenden findest du eine sehr einfache Form des Counting Sort-Quellcodes \u2013 diese funktioniert ausschlie\u00dflich f\u00fcr nicht-negative <code>int<\/code>-Primitive (z. B. f\u00fcr das Array aus dem Beispiel oben).<\/p>\n\n\n\n<p>Zun\u00e4chst wird \u00fcber die <code>findMax()<\/code>-Methode das gr\u00f6\u00dfte Element im Array gefunden. Dann wird das Hilfsarray <code>counts<\/code> der entsprechenden Gr\u00f6\u00dfe angelegt, wobei die Gr\u00f6\u00dfe um eins gr\u00f6\u00dfer ist als das gr\u00f6\u00dfte Element, um auch die 0 mitz\u00e4hlen zu k\u00f6nnen.<\/p>\n\n\n\n<p>(Bei kleineren Zahlenr\u00e4umen wie <code>byte<\/code> und <code>short<\/code> kann das Ermitteln des Maximums auch weggelassen werden und direkt ein Array in der Gr\u00f6\u00dfe des Zahlenraums erstellt werden.)<\/p>\n\n\n\n<p>Im mit \"Phase 1\" kommentierten Block werden die Elemente gez\u00e4hlt, so dass das <code>counts<\/code>-Array schlie\u00dflich das Histogramm enth\u00e4lt.<\/p>\n\n\n\n<p>Im mit \"Phase 2\" kommentierten Block werden die Elemente in aufsteigender Reihenfolge und entsprechend der im Histogramm hinterlegten H\u00e4ufigkeit zur\u00fcck in das zu sortierende Array geschrieben.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">CountingSortSimple<\/span> <\/span>{\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">sort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> maxValue = findMax(elements);\n    <span class=\"hljs-keyword\">int<\/span>&#091;] counts = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;maxValue + <span class=\"hljs-number\">1<\/span>];\n\n    <span class=\"hljs-comment\">\/\/ Phase 1: Count<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> element : elements) {\n      counts&#091;element]++;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Phase 2: Write results back<\/span>\n    <span class=\"hljs-keyword\">int<\/span> targetPos = <span class=\"hljs-number\">0<\/span>;\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; counts.length; i++) {\n      <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> j = <span class=\"hljs-number\">0<\/span>; j &lt; counts&#091;i]; j++) {\n        elements&#091;targetPos++] = i;\n      }\n    }\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">findMax<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> max = <span class=\"hljs-number\">0<\/span>;\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> element : elements) {\n      <span class=\"hljs-keyword\">if<\/span> (element &lt; <span class=\"hljs-number\">0<\/span>) {\n        <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"This implementation does not support negative values.\"<\/span>);\n      }\n      <span class=\"hljs-keyword\">if<\/span> (element &gt; max) {\n        max = element;\n      }\n    }\n    <span class=\"hljs-keyword\">return<\/span> max;\n  }\n\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Das Maximum k\u00f6nnte auch mittels <code>Arrays.stream(elements).max().getAsInt()<\/code> ermittelt werden. Dann m\u00fcssten wir allerdings die Pr\u00fcfung auf negative Werte entweder weglassen oder in einem separaten Schritt durchf\u00fchren.<\/p>\n\n\n\n<p>Den Code findest du im GitHub-Repository in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/countingsort\/CountingSortSimple.java\" target=\"_blank\">CountingSortSimple<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-quellcode-auch-fuer-negative-zahlen\">Counting Sort Quellcode auch f\u00fcr negative Zahlen<\/h3>\n\n\n\n<p>Sollen auch negative Zahlen erlaubt sein, wird der Code etwas komplizierter, da wir mit einem sogenannten <em>Offset<\/em> arbeiten m\u00fcssen, um die zu sortierende Zahl auf die Position im Hilfsarray zu mappen. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Berechnung des Offset<\/h4>\n\n\n\n<p>Der Offset ist: null minus die kleinste zu sortierende Zahl.<\/p>\n\n\n\n<p>Ist beispielsweise -5 die kleinste zu sortierende Zahl, dann ist der Offset 5, d. h. der Index im Hilfsarray ist jeweils die zu sortierende Zahl plus 5.<\/p>\n\n\n\n<p>Die -5 wird also beispielsweise an Position -5+5 = 0 gez\u00e4hlt; die 0 wird an Position 0+5 = 5 gez\u00e4hlt; die 11 wird an Position 11+5 = 16 gez\u00e4hlt.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Quellcode<\/h4>\n\n\n\n<p>Den folgenden Quellcode findest du in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/countingsort\/CountingSort.java\">CountingSort<\/a> im GitHub-Repository. Er \u00e4hnelt dem oben gezeigte Quellcode bis auf folgende Unterschiede:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die Methode <code>findMax()<\/code> ist ersetzt durch die Methode <code>findBoundaries()<\/code>, die nicht nur den Maximal-, sondern auch den Minimalwert zur\u00fcckgibt (bei kleinen Zahlenr\u00e4umen wie <code>byte<\/code> und <code>short<\/code> kann das Ermitteln der Grenzwerte weggelassen werden und direkt ein Array in der Gr\u00f6\u00dfe des Zahlenraums erstellt werden).<\/li>\n\n\n\n<li>Beim Zugriff auf das <code>counts<\/code>-Array in der Z\u00e4hlphase wird dem jeweiligen Index der Offset <code>-boundaries.min<\/code> hinzuaddiert (bzw. <code>-Byte.MIN_VALUE<\/code> oder <code>-Short.MIN_VALUE<\/code>).<\/li>\n\n\n\n<li>Beim Zur\u00fcckschreiben der sortierten Zahlen in das Array wird der Offset wieder abgezogen, indem <code>boundaries.min<\/code> (bzw. <code>Byte.MIN_VALUE<\/code> oder <code>Short.MIN_VALUE<\/code>) addiert wird.<\/li>\n<\/ul>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">CountingSort<\/span> <\/span>{\n\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">int<\/span> MAX_VALUE_TO_SORT = Integer.MAX_VALUE \/ <span class=\"hljs-number\">2<\/span>;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">int<\/span> MIN_VALUE_TO_SORT = Integer.MIN_VALUE \/ <span class=\"hljs-number\">2<\/span>;\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">sort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    Boundaries boundaries = findBoundaries(elements);\n    <span class=\"hljs-keyword\">int<\/span>&#091;] counts = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;boundaries.max - boundaries.min + <span class=\"hljs-number\">1<\/span>];\n\n    <span class=\"hljs-comment\">\/\/ Phase 1: Count<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> element : elements) {\n      counts&#091;element - boundaries.min]++;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Phase 2: Write results back<\/span>\n    <span class=\"hljs-keyword\">int<\/span> targetPos = <span class=\"hljs-number\">0<\/span>;\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; counts.length; i++) {\n      <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> j = <span class=\"hljs-number\">0<\/span>; j &lt; counts&#091;i]; j++) {\n        elements&#091;targetPos++] = i + boundaries.min;\n      }\n    }\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> Boundaries <span class=\"hljs-title\">findBoundaries<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> min = Integer.MAX_VALUE;\n    <span class=\"hljs-keyword\">int<\/span> max = Integer.MIN_VALUE;\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> element : elements) {\n      <span class=\"hljs-keyword\">if<\/span> (element &gt; MAX_VALUE_TO_SORT) {\n        <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"Element \"<\/span> + element +\n              <span class=\"hljs-string\">\" is greater than maximum \"<\/span> + MAX_VALUE_TO_SORT);\n      }\n      <span class=\"hljs-keyword\">if<\/span> (element &lt; MIN_VALUE_TO_SORT) {\n        <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"Element \"<\/span> + element +\n              <span class=\"hljs-string\">\" is less than minimum \"<\/span> + MIN_VALUE_TO_SORT);\n      }\n      <span class=\"hljs-keyword\">if<\/span> (element &gt; max) {\n        max = element;\n      }\n      <span class=\"hljs-keyword\">if<\/span> (element &lt; min) {\n        min = element;\n      }\n    }\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">new<\/span> Boundaries(min, max);\n  }\n\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">Boundaries<\/span> <\/span>{\n    <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">int<\/span> min;\n    <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">int<\/span> max;\n\n    <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">Boundaries<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> min, <span class=\"hljs-keyword\">int<\/span> max)<\/span> <\/span>{\n      <span class=\"hljs-keyword\">this<\/span>.min = min;\n      <span class=\"hljs-keyword\">this<\/span>.max = max;\n    }\n  }\n\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Diese Variante hat nicht nur den Vorteil auch negative Zahlen z\u00e4hlen zu k\u00f6nnen, sondern belegt auch weniger zus\u00e4tzlichen Speicher als die erste Variante, falls der Zahlenraum nicht bei 0 beginnt: F\u00fcr Zahlen von 1.000 bis 2.000 beispielweise w\u00fcrde die erste Variante ein Hilfsarray mit 2.001 Feldern ben\u00f6tigen, Variante 2 hingegen nur 1.001 Felder.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-algorithmus-allgemeine-form\">Counting Sort Algorithmus (Allgemeine Form)<\/h2>\n\n\n\n<p>Mit Counting Sort k\u00f6nnen nicht nur Arrays von Primitiven (also <code>bytes<\/code>, <code>ints<\/code>, <code>longs<\/code>, <code>doubles<\/code>, etc.) sortiert werden, sondern auch Arrays von Objekten. Dazu m\u00fcssen wir den Algorithmus, wie im folgenden Abschnitt beschrieben, erweitern.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"allgemeiner-algorithmus-phase-1-elemente-zaehlen\">Allgemeiner Algorithmus \u2013 Phase 1: Elemente z\u00e4hlen<\/h3>\n\n\n\n<p>Phase 1, die Z\u00e4hlphase bleibt quasi unver\u00e4ndert. Statt der Objekte selbst werden nun deren Schl\u00fcsselwerte (z. B. ermittelt durch eine <code>getKey()<\/code>-Methode) gez\u00e4hlt.<\/p>\n\n\n\n<p>Das Array in der folgenden Grafik referenziert Objekte, deren Keys den Zahlen aus dem vorherigen Beispiel entsprechen, also 3, 7, 4, 6, 6, usw:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1410\" height=\"344\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - zu sortierendes Array\" class=\"wp-image-15806\" style=\"width:705px;height:172px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array.png 1410w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-224x55.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-336x82.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-504x123.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-672x164.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-400x98.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-600x146.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-800x195.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-944x230.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_array-1200x293.png 1200w\" sizes=\"(max-width: 1410px) 100vw, 1410px\" \/><\/figure>\n<\/div>\n\n\n<p>Entsprechend gleicht das daraus entstandene Histogramm dem aus dem ersten Beispiel:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"926\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Histogramm\" class=\"wp-image-15807\" style=\"width:463px;height:206px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram.png 926w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram-224x100.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram-336x149.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram-504x224.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram-672x299.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram-400x178.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram-600x267.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_histogram-800x356.png 800w\" sizes=\"(max-width: 926px) 100vw, 926px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"allgemeiner-algorithmus-phase-2-histogramm-aggregieren\">Allgemeiner Algorithmus \u2013 Phase 2: Histogramm aggregieren<\/h3>\n\n\n\n<p>Jetzt wird der Unterschied zum vereinfachten Algorithmus deutlich: Wir wissen jetzt zwar, dass das Element mit dem Key 0 <em>ein<\/em> Mal vorkommt, k\u00f6nnen aber nicht einfach eine 0 in das zu sortierende Array schreiben \u2013 vielmehr ben\u00f6tigen wir das <em>Objekt<\/em> mit dem Key 0!<\/p>\n\n\n\n<p>Um dies <em>effizient<\/em> zu finden, aggregieren wir zun\u00e4chst die Werte im Histogramm. Dazu iterieren wir, beginnend bei Index 1, \u00fcber das Hilfsarray und addieren zu jedem Feld den Wert des linken Nachbarfeldes.<\/p>\n\n\n\n<p>An Position 1 addieren wir zur 0 den Wert von Feld 0, also die 1. Die Summe ist 1:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1568\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 1\" class=\"wp-image-15817\" style=\"width:784px;height:206px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1.png 1568w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-224x59.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-336x88.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-504x132.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-672x177.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-400x105.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-600x158.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-800x210.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-944x248.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step1-1200x315.png 1200w\" sizes=\"(max-width: 1568px) 100vw, 1568px\" \/><\/figure>\n<\/div>\n\n\n<p>An Position 2 addieren wir zur 1 die 1 von Feld 1 und erhalten eine 2:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1568\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 2\" class=\"wp-image-15819\" style=\"width:784px;height:206px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2.png 1568w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-224x59.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-336x88.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-504x132.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-672x177.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-400x105.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-600x158.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-800x210.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-944x248.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step2-1200x315.png 1200w\" sizes=\"(max-width: 1568px) 100vw, 1568px\" \/><\/figure>\n<\/div>\n\n\n<p>Zur 3 an Position 3 addieren wir die 2 von Feld 2 \u2013 die Summe ist 5:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1568\" height=\"414\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 3\" class=\"wp-image-15820\" style=\"width:784px;height:207px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3.png 1568w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-224x59.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-336x89.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-504x133.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-672x177.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-400x106.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-600x158.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-800x211.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-944x249.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step3-1200x317.png 1200w\" sizes=\"(max-width: 1568px) 100vw, 1568px\" \/><\/figure>\n<\/div>\n\n\n<p>Und so fahren wir fort, bis wir letztendlich zur 1 in Feld 9 die 14 von Feld 8 addieren und 15 erhalten:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1568\" height=\"666\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 9\" class=\"wp-image-15821\" style=\"width:784px;height:333px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9.png 1568w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-224x95.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-336x143.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-504x214.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-672x285.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-400x170.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-600x255.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-800x340.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-944x401.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase2_aggregation_step9-1200x510.png 1200w\" sizes=\"(max-width: 1568px) 100vw, 1568px\" \/><\/figure>\n<\/div>\n\n\n<p>Dieses aggregierte Histogramm sagt uns jetzt nicht mehr, wie <em>oft<\/em> die Objekte mit bestimmten Keys vorkommen, sondern <em>an welche Position<\/em> das letzte Element mit dem entsprechenden Key geh\u00f6rt. Die Position ist hierbei 1-basiert, nicht 0-basiert.<\/p>\n\n\n\n<p>Beispielsweise geh\u00f6rt das Objekt mit Key 0 an Position 1 (entspricht Index 0 im Array), das Objekt mit Key 2 an Position 2 (Array-Index 1) und die drei Objekte mit Key 3 an die Positionen 3, 4 und 5 (Array-Indexe 2, 3, 4).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"allgemeiner-algorithmus-phase-3-objekte-sortiert-zurueckschreiben\">Allgemeiner Algorithmus \u2013 Phase 3: Objekte sortiert zur\u00fcckschreiben<\/h3>\n\n\n\n<p>Um die Objekte zu sortieren, ben\u00f6tigen wir ein zus\u00e4tzliches Array in der Gr\u00f6\u00dfe des Eingabearrays:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1600\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 3 - Zielarray\" class=\"wp-image-15825\" style=\"width:800px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0.png 1600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-224x106.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-336x160.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-504x239.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-672x319.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-400x190.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-600x285.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-800x380.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-944x448.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step0-1200x570.png 1200w\" sizes=\"(max-width: 1600px) 100vw, 1600px\" \/><\/figure>\n<\/div>\n\n\n<p>Wir iterieren nun r\u00fcckw\u00e4rts \u00fcber das zu sortierende Array und schreiben jedes Objekt im Zielarray an diejenige Position, die durch das Hilfsarray angezeigt wird. Wir dekrementieren den entsprechenden Wert im Hilfsarray um 1, um ggf. das n\u00e4chste Objekt mit demselben Key ein Feld weiter links einzusortieren.<\/p>\n\n\n\n<p>Beginnen wir im Eingabearray ganz rechts \u2013 mit dem Objekt mit dem Key 8. Im Hilfsarray steht an Position 8 der Wert 14. Wir dekrementieren den Wert auf 13 und kopieren das Objekt mit dem Key 8 in das Zielarray an Position 13 (zur Erinnerung: die Positionsangaben im Hilfsarray sind 1-basiert, deshalb schreiben wir auf Position 13, nicht 14).<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1524\" height=\"1110\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 1\" class=\"wp-image-15831\" style=\"width:762px;height:555px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3.png 1524w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-224x163.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-336x245.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-504x367.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-672x489.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-400x291.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-600x437.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-800x583.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-944x688.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step1-v3-1200x874.png 1200w\" sizes=\"(max-width: 1524px) 100vw, 1524px\" \/><\/figure>\n<\/div>\n\n\n<p>Das zweite Objekt von rechts hat den Key 2. Im Hilfsarray steht an Position 2 der Wert 2. Wir dekrementieren den Wert im Hilfsarray auf 1 und kopieren das Objekt an die entsprechende Position im Zielarray:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1410\" height=\"1106\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 2\" class=\"wp-image-15833\" style=\"width:705px;height:553px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2.png 1410w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-224x176.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-336x264.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-504x395.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-672x527.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-400x314.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-600x471.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-800x628.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-944x740.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step2-1200x941.png 1200w\" sizes=\"(max-width: 1410px) 100vw, 1410px\" \/><\/figure>\n<\/div>\n\n\n<p>Das n\u00e4chste Objekt hat den Key 6. Im Hilfsarray steht an Position 6 die 11. Wir dekrementieren das Feld auf 10 und kopieren das Objekt nach Feld 10 im Zielarray:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1410\" height=\"1110\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 3\" class=\"wp-image-15942\" style=\"width:705px;height:555px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2.png 1410w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-224x176.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-336x265.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-504x397.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-672x529.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-400x315.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-600x472.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-800x630.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-944x743.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting_sort_general_algorithm_phase3_step3-v2-1200x945.png 1200w\" sizes=\"(max-width: 1410px) 100vw, 1410px\" \/><\/figure>\n<\/div>\n\n\n<p>Derselben Logik folgend kopieren wir das Objekt mit dem Key 9 an Position 14 des Zielarrays:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1414\" height=\"1106\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 4\" class=\"wp-image-15837\" style=\"width:707px;height:553px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4.png 1414w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-224x175.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-336x263.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-504x394.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-672x526.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-400x313.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-600x469.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-800x626.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-944x738.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step4-1200x939.png 1200w\" sizes=\"(max-width: 1414px) 100vw, 1414px\" \/><\/figure>\n<\/div>\n\n\n<p>Es folgt eine weitere 6. Im Hilfsarray steht an Position 6 jetzt die 10 (nachdem wir zuvor dort die 11 dekrementiert hatten). Wir dekrementieren das Feld erneut auf 9 und kopieren das Objekt nach Position 9 im Zielarray, also links neben das andere Objekt mit dem Key 6:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1410\" height=\"1110\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 5\" class=\"wp-image-15840\" style=\"width:705px;height:555px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5.png 1410w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-224x176.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-336x265.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-504x397.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-672x529.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-400x315.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-600x472.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-800x630.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-944x743.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step5-1200x945.png 1200w\" sizes=\"(max-width: 1410px) 100vw, 1410px\" \/><\/figure>\n<\/div>\n\n\n<p>Wir wiederholen diese Schritte f\u00fcr alle Elemente und kommen als letztes zum Objekt mit dem Key 3. An Feld 3 im Hilfsarray steht nun eine 3. Diese dekrementieren wir auf 2 und kopieren das Objekt auf Position 2, die letzte freie Position, des Zielarrays:<\/p>\n\n\n<div class=\"wp-block-image hc-image-margins\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1534\" height=\"1109\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15.png\" alt=\"Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 15\" class=\"wp-image-15841\" style=\"width:767px;height:555px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15.png 1534w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-224x162.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-336x243.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-504x364.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-672x486.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-400x289.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-600x434.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-800x578.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-944x682.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_general_algorithm_phase3_step15-1200x868.png 1200w\" sizes=\"(max-width: 1534px) 100vw, 1534px\" \/><\/figure>\n<\/div>\n\n\n<p>Die Objekte sind sortiert, der Algorithmus ist beendet.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-java-code-beispiel-allgemeine-form\">Counting Sort Java Code Beispiel (Allgemeine Form)<\/h2>\n\n\n\n<p>Der folgende Code demonstriert die allgemeine Form von Counting Sort der Einfachheit halber an <code>int<\/code>-Primitiven. Die <code>findMax()<\/code>-Methode gleicht der im ersten Quellcode-Beispiel, ich habe sie daher hier nicht noch einmal mit abgedruckt.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">CountingSortGeneral<\/span> <\/span>{\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">sort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> maxValue = findMax(elements);\n    <span class=\"hljs-keyword\">int<\/span>&#091;] counts = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;maxValue + <span class=\"hljs-number\">1<\/span>];\n\n    <span class=\"hljs-comment\">\/\/ Phase 1: Count<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> element : elements) {\n      counts&#091;element]++;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Phase 2: Aggregate<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">1<\/span>; i &lt;= maxValue; i++) {\n      counts&#091;i] += counts&#091;i - <span class=\"hljs-number\">1<\/span>];\n    }\n\n    <span class=\"hljs-comment\">\/\/ Phase 3: Write to target array<\/span>\n    <span class=\"hljs-keyword\">int<\/span>&#091;] target = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;elements.length];\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = elements.length - <span class=\"hljs-number\">1<\/span>; i &gt;= <span class=\"hljs-number\">0<\/span>; i--) {\n      <span class=\"hljs-keyword\">int<\/span> element = elements&#091;i];\n      target&#091;--counts&#091;element]] = element;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Copy target back to input array<\/span>\n    System.arraycopy(target, <span class=\"hljs-number\">0<\/span>, elements, <span class=\"hljs-number\">0<\/span>, elements.length);\n  }\n\n  &#091;...]\n\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Du findest den Quellcode in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/countingsort\/CountingSortGeneral.java\" target=\"_blank\" rel=\"noopener\">CountingSortGeneral<\/a> im GitHub-Repository.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"counting-sort-zeitkomplexitaet\">Counting Sort Zeitkomplexit\u00e4t<\/h2>\n\n\n\n<p>Die <a href=\"\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">Zeitkomplexit\u00e4t<\/a> von Counting Sort ist aufgrund des sehr einfachen Algorithmus leicht bestimmbar.<\/p>\n\n\n\n<p>Sei <em>n<\/em> die Anzahl der zu sortierenden Elemente und <em>k<\/em> die Gr\u00f6\u00dfe des Zahlenraums der Elemente.<\/p>\n\n\n\n<p>Der Algorithmus enth\u00e4lt eine oder mehrere Schleifen, die bis <em>n<\/em> iterieren und eine Schleife, die bis <em>k<\/em> iteriert.<\/p>\n\n\n\n<p>Konstante Faktoren sind f\u00fcr die Zeitkomplexit\u00e4t irrelevant; somit gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Counting Sort betr\u00e4gt: <em>O(n + k)<\/em><\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-des-java-counting-sort-beispiels\">Laufzeit des Java Counting Sort Beispiels<\/h3>\n\n\n\n<p>Das GitHub-Repository enth\u00e4lt das Programm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/UltimateTest.java\" target=\"_blank\">UltimateTest<\/a>, mit dem wir die Geschwindigkeit von Counting Sort und aller anderen Sortieralgorithmen dieser Artikelserie messen k\u00f6nnen.<\/p>\n\n\n\n<p>Die folgende Tabelle zeigt die ben\u00f6tigte Zeit zum Sortieren von unsortierten sowie aufsteigend und absteigend vorsortierten Elementen f\u00fcr die jeweils angegebene Anzahl von Elementen <em>n<\/em>, die in diesen Messungen auch der Gr\u00f6\u00dfe des Zahlenraums <em>k<\/em> entspricht:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n, k<\/th><th class=\"has-text-align-right\" data-align=\"right\">unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">aufsteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">absteigend<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">33.554.432<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.276 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">195 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">210 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">67.108.864<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.857 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">381 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">388 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">134.217.728<\/td><td class=\"has-text-align-right\" data-align=\"right\">6.087 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">745 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">766 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">268.435.456<\/td><td class=\"has-text-align-right\" data-align=\"right\">12.684 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.477 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.529 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">536.870.912<\/td><td class=\"has-text-align-right\" data-align=\"right\">27.249 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.945 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.039 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Das vollst\u00e4ndige Ergebnis findest du in der Datei <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-08-30\/Test_Results_Counting_Sort.log\" target=\"_blank\" rel=\"noopener\">Test_Results_Counting_Sort.log<\/a>. Das folgende Diagramm stellt die Messwerte grafisch dar:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1514\" height=\"878\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime.png\" alt=\"Counting Sort - Laufzeit\" class=\"wp-image-15880\" style=\"width:757px;height:439px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime.png 1514w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-224x130.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-336x195.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-504x292.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-672x390.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-400x232.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-600x348.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-800x464.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-944x547.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/08\/counting_sort_runtime-1200x696.png 1200w\" sizes=\"(max-width: 1514px) 100vw, 1514px\" \/><\/figure>\n<\/div>\n\n\n<p>Es l\u00e4sst sich folgendes ablesen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Vorsortierte Ausgangsfolgen mit einer halben Milliarde Elemente werden etwa neun mal so schnell sortiert wie unsortierte.<\/li>\n\n\n\n<li>Bei vorsortierten Ausgangsfolgen entsprechen die Messwerte der erwarteten linearen Zeitkomplexit\u00e4t <em>O(n + k)<\/em>.<\/li>\n\n\n\n<li>F\u00fcr unsortierte Ausgangsfolgen liegen die Messwerte etwas dar\u00fcber: Bei einer Verdopplung der Arraygr\u00f6\u00dfe nimmt die ben\u00f6tigte Zeit etwa um Faktor 2,1 bis 2,2 zu.<\/li>\n\n\n\n<li>Absteigend sortierte Ausgangsfolgen werden minimal langsamer sortiert als aufsteigend vorsortierte.<\/li>\n<\/ul>\n\n\n\n<p>Wenn Elemente nicht umsortiert, sondern gez\u00e4hlt und einmal komplett neu angeordnet werden, d\u00fcrfte doch die Ausgangsreihenfolge keine Auswirkung auf die zum Sortieren ben\u00f6tigte Zeit haben!?<\/p>\n\n\n\n<p>Mit dem Programm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/CountOperations.java\" target=\"_blank\">CountOperations<\/a> k\u00f6nnen wir messen, wie viele Operationen f\u00fcr das Sortieren ben\u00f6tigt werden. Und tats\u00e4chlich best\u00e4tigt das Ergebnis (s. Datei <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-08-30\/CountOperations_Counting_Sort.log\" target=\"_blank\">CountOperations_Counting_Sort.log<\/a>):<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die Anzahl der Operationen ist unabh\u00e4ngig von der Ausgangsreihenfolge der Elemente.<\/li>\n\n\n\n<li>Die Anzahl der Operationen entspricht der erwarteten Zeitkomplexit\u00e4t O(n + k), steigt also linear mit der Anzahl der zu sortierenden Elememte und der Gr\u00f6\u00dfe des Zahlenraums.<\/li>\n<\/ul>\n\n\n\n<p>Wie kommen dann diese abweichenden Messwerte zustande? Erkl\u00e4rungen findest du in den folgenden Abschnitten.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"warum-ist-counting-sort-fuer-vorsortierte-elemente-schneller-als-fuer-unsortierte-elemente\">Warum ist Counting Sort f\u00fcr vorsortierte Elemente schneller als f\u00fcr unsortierte Elemente?<\/h3>\n\n\n\n<p>Ein Hilfsarray mit einer halben Milliarde Elemente ist 2 GB gro\u00df. Wenn dessen Elemente in zuf\u00e4lliger Reihenfolge inkrementiert werden, muss beinahe f\u00fcr jedes Element eine neue Cache-Line (typischerweise 64 Byte gro\u00df) zwischen RAM und CPU-Cache ausgetauscht werden. Die Wahrscheinlichkeit, dass die ben\u00f6tigte Cache-Line im CPU-Cache liegt, ist umso niedriger, je gr\u00f6\u00dfer das Array ist.<\/p>\n\n\n\n<p>Wird das Array hingegen von vorne nach hinten (oder von hinten nach vorne) inkrementiert, k\u00f6nnen jeweils 16 aufeinanderfolgende <code>int<\/code>-Werte in einem 64-Byte-Block aus dem RAM geladen und wieder dorthin geschrieben werden.<\/p>\n\n\n\n<p>Es wird nicht ganz eine Beschleunigung um Faktor 16 erreicht, aber zumindest eine um ca. Faktor neun.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"warum-erreicht-counting-sort-in-der-praxis-keine-lineare-zeitkomplexitaet-fuer-unsortierte-ausgangsfolgen\">Warum erreicht Counting Sort in der Praxis keine lineare Zeitkomplexit\u00e4t f\u00fcr unsortierte Ausgangsfolgen?<\/h3>\n\n\n\n<p>Je gr\u00f6\u00dfer das zu sortierende Array, desto h\u00f6her wird bei einem unsortierten Ausgangsarray das Verh\u00e4ltnis von Cache Misses zu Cache Hits beim Zugriff auf das Hilfsarray (denn die Gr\u00f6\u00dfe des CPU-Caches bleibt ja gleich).<\/p>\n\n\n\n<p>Bei einem doppelt so gro\u00dfen Array haben wir also nicht doppelt so viele Cache Misses, sondern etwas mehr als doppelt so viele. Dementsprechend erh\u00f6ht sich die ben\u00f6tigte Zeit auch um etwas mehr als Faktor zwei.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"warum-ist-counting-sort-fuer-aufsteigend-sortierte-elemente-schneller-als-fuer-absteigend-sortierte\">Warum ist Counting Sort f\u00fcr aufsteigend sortierte Elemente schneller als f\u00fcr absteigend sortierte?<\/h3>\n\n\n\n<p>Bei aufsteigend sortierten Elementen werden diese nicht ver\u00e4ndert, m\u00fcssen also nicht zur\u00fcck in den RAM geschrieben werden. Bei absteigend sortierten Elementen \u00e4ndert sich jedes Element des Arrays, entsprechend muss das gesamte Array einmal zur\u00fcck in den RAM geschrieben werden.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"weitere-eigenschaften-von-counting-sort\">Weitere Eigenschaften von Counting Sort<\/h2>\n\n\n\n<p>In diesem Kapitel bestimmen wir die Platzkomplexit\u00e4t, die Stabilit\u00e4t und die Parallelisierbarkeit von Counting Sort.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"platzkomplexitaet-von-counting-sort\">Platzkomplexit\u00e4t von Counting Sort<\/h3>\n\n\n\n<p>Der vereinfachte Algorithmus ben\u00f6tigt ein zus\u00e4tzliches Array der Gr\u00f6\u00dfe <em>k<\/em>; es gilt entsprechend:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Platzkomplexit\u00e4t des vereinfachten Counting Sort Algorithmus ist: <em>O(k)<\/em><\/p>\n\n\n\n<p>Der allgemeine Algorithmus ben\u00f6tigt neben dem Hilfsarray der Gr\u00f6\u00dfe <em>k<\/em> ein tempor\u00e4res Zielarray der Gr\u00f6\u00dfe <em>n<\/em>; somit gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Platzkomplexit\u00e4t des allgemeinen Counting Sort Algorithmus ist: <em>O(n + k)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stabilitaet-von-counting-sort\">Stabilit\u00e4t von Counting Sort<\/h3>\n\n\n\n<p>Die allgemeine Form des Counting Sort Algorithmus iteriert in Phase 3 von rechts nach links \u00fcber das Eingabearray und kopiert dabei Objekte mit demselben Key ebenfalls von rechts nach links in das Ausgabearray. Somit gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Counting Sort ist ein stabiler Sortieralgorithmus.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"parallelisierbarkeit-von-counting-sort\">Parallelisierbarkeit von Counting Sort<\/h3>\n\n\n\n<p>Counting Sort kann parallelisiert werden, in dem das Eingabearray in so viele Partitionen geteilt wird, wie Prozessoren zur Verf\u00fcgung stehen.<\/p>\n\n\n\n<p>In Phase 1 z\u00e4hlt jeder Prozessor die Elemente \"seiner\" Partition in einem separatem Hilfsarray.<\/p>\n\n\n\n<p>In Phase 2 werden alle Hilfsarrays zu einem aufaddiert.<\/p>\n\n\n\n<p>In Phase 3 kopiert jeder Prozessor die Elemente \"seiner\" Partition ins Zielarray. Das Dekrementieren und Auslesen der Felder im Hilfsarray muss dabei atomar erfolgen.<\/p>\n\n\n\n<p>Durch die Parallelisierung kann nicht mehr garantiert werden, dass Elemente mit gleichem Key in ihrer urspr\u00fcnglichen Reihenfolge ins Zielarray kopiert werden. <\/p>\n\n\n\n<p>Paralleles Counting Sort ist dementsprechend nicht stabil.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung\">Zusammenfassung<\/h2>\n\n\n\n<p>Counting Sort ist ein sehr effizienter, stabiler Sortieralgorithmus mit einer Zeit- und Platzkomplexit\u00e4t von <em>O(n + k)<\/em>.<\/p>\n\n\n\n<p>Counting Sort wird haupts\u00e4chlich f\u00fcr kleine Zahlenr\u00e4ume eingesetzt. Im JDK beispielsweise f\u00fcr:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>byte<\/code>-Arrays mit mehr als 64 Elementen (darunter wird Insertion Sort eingesetzt)<\/li>\n\n\n\n<li><code>short<\/code>- oder <code>char<\/code>-Arrays mit mehr als 1.750 Elementen (darunter wird Insertion Sort oder Dual-Pivot Quicksort verwendet)<\/li>\n<\/ul>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>Alle bisher vorgestellten Sortierverfahren basieren auf dem Vergleich zweier Elemente auf kleiner, gr\u00f6\u00dfer oder gleich. Dass es auch sogenannte nicht-vergleichsbasierte Sortierverfahren gibt, erf\u00e4hrst du in diesem Artikel \u00fcber Counting Sort.<\/p>\n","protected":false},"author":1,"featured_media":43251,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie funktioniert Counting Sort? Mit Illustrationen und Quellcode. Wie bestimmt man die Zeitkomplexit\u00e4t (ohne komplizierte Mathematik)?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":20318,"_post_count":0,"footnotes":""},"categories":[127],"tags":[129],"class_list":["post-12217","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-sortieralgorithmen"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/09\/counting-sort-java-feature-image.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":1,"uagb_excerpt":"Alle bisher vorgestellten Sortierverfahren basieren auf dem Vergleich zweier Elemente auf kleiner, gr\u00f6\u00dfer oder gleich. Dass es auch sogenannte nicht-vergleichsbasierte Sortierverfahren gibt, erf\u00e4hrst du in diesem Artikel \u00fcber Counting Sort.","public_identification_id":"7d47b45c32ea494aaa9b59810375b692","private_identification_id":"69eda97403d94823b06e6ac9e9086097","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12217","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=12217"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12217\/revisions"}],"predecessor-version":[{"id":52518,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12217\/revisions\/52518"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43251"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=12217"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=12217"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=12217"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}