{"id":4061,"date":"2024-10-19T17:11:48","date_gmt":"2024-10-19T15:11:48","guid":{"rendered":"https:\/\/www.capri-soft.de\/blog\/?p=4061"},"modified":"2024-10-19T17:11:48","modified_gmt":"2024-10-19T15:11:48","slug":"algorithmen-und-datenstrukturen-der-counting-sort-in-java","status":"publish","type":"post","link":"https:\/\/www.capri-soft.de\/blog\/?p=4061","title":{"rendered":"Algorithmen und Datenstrukturen: Der Counting Sort in Java"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Der Algorithmus<\/h2>\n\n\n\n<p>Der Counting Sort ist ein <strong>Out-of-place-Sortieralgorithmus<\/strong>, <strong>da er das<\/strong> zu sortierende <strong>Array <\/strong>im Gegensatz zu Quick Sort oder Bubble Sort <strong>nicht direkt sortiert, sondern vorher eine Speicherkopie anlegt<\/strong>, die im Abschluss auf das zu sortierende Array kopiert wird.<\/p>\n\n\n\n<p>Der Algorithmus ist genau dann effizient, wenn man viele (doppelte) Zahlen in einem kleinem Wertebereich \/ einer engen Min-\/Max-Range sortieren m\u00f6chte. <\/p>\n\n\n\n<p>Wenn man z.B.  ein Array mit dem Aufkommen von Menschen nach Alter in der deutschen Bev\u00f6lkerung sortieren m\u00f6chte, so h\u00e4tte man eine Array-Gr\u00f6\u00dfe von ca. 80 Millionen Eintr\u00e4gen. Da es aber<a href=\"https:\/\/de.wikipedia.org\/wiki\/Liste_der_%C3%A4ltesten_lebenden_Menschen\"> keine Menschen \u00fcber 120 Jahren in Deutschland gibt<\/a>, oder der \u00e4lteste noch lebende Mensch in Deutschland aktuell j\u00fcnger als 120 Jahre ist, kann man den Wertebereich zwischen 0 und 120 Jahren einschr\u00e4nken. <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Kleiner Wertebereich<\/strong>: Alter zwischen 0 und 120 Jahren.<\/li>\n\n\n\n<li><strong>Gro\u00dfes Array<\/strong>: 80 Millionen Eintr\u00e4ge f\u00fcr jeden Menschen<\/li>\n<\/ul>\n\n\n\n<p>F\u00fcr diese F\u00e4lle eignet sich der Counting Sort Algorithmus ausgezeichnet, da er nach der folgenden Vorgehensweise vor geht:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Ermittle den maximalen Wert des Wertebereichs f\u00fcr das Histogramm (z.B. h\u00f6chstes Alter 120 Jahre)<\/li>\n\n\n\n<li>Initialisiere ein sortiertes Histogramm als Array mit 0-Werten.<\/li>\n\n\n\n<li>Laufe das gro\u00dfe Array in einer O(n)-Schleife durch (z.B. das Array mit den 80 Mio. Menschen)\n<ul class=\"wp-block-list\">\n<li>Z\u00e4hle die Histogramm-Array-Werte \u00fcber die Vorkommnisse\/H\u00e4ufigkeiten beim Durchlaufen um 1 nach oben, je nachdem welche Zahl bei dem Durchlauf gefunden wird<\/li>\n\n\n\n<li>Laufe das erstellte Histogramm-Array von links nach rechts durch und f\u00fcge die Vorkommnisse der Zahlen in das Ziel-Array ein, so dass bei 2x der Zahl 1 und 4x der Zahl 2 so etwas rauskommt: 1;1;2;2;2;2<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Auf diese Weise wurde anhand des sortierten Histogramm-Arrays die Zahlenmenge sortiert<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: java; title: ; notranslate\" title=\"\">\npackage AlgoDat;\n\nimport java.util.Arrays;\n\npublic class CountingSort {\n    \/\/ Zu sortierendes Array\n    private int myArray&#x5B;] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};\n\n    \/\/ H\u00e4lt die Klasse als instanziertes Objekt\n    @SuppressWarnings(&quot;unused&quot;)\n    private static CountingSort program;\n    private java.util.Random rnd = new java.util.Random();\n\n    \/\/ Hilfsfunktion f\u00fcr das Ausgeben des Arrays\n    public void OutputOfIntArray(int myArray&#x5B;])\n    {\n        if (myArray != null)\n        {\n            for (int i = 0; i &lt; myArray.length; i++) {\n                if (i &gt; 0) System.out.print(&quot;;&quot;);\n                System.out.print(myArray&#x5B;i]);\n            }\n\n            System.out.println();\n        }\n    }\n\n    \/\/ Generiert ein zuf\u00e4lliges Integer-Array der Gr\u00f6\u00dfe size mit Werten zwischen 0 und upperLimit\n    public int&#x5B;] generateIntegerArrayOfSize(int size, int upperLimit)\n    {       \n        int&#x5B;] generatedArray = new int&#x5B;size];\n        \n        for (int i = 0; i &lt; generatedArray.length; i++)\n        {\n            generatedArray&#x5B;i] = rnd.nextInt(upperLimit);\n        }\n\n        return generatedArray;\n    }\n\n    \/\/ Konstruktor\n    public CountingSort()\n    {\n        System.out.println(&quot;Kleines Array&quot;);\n        System.out.println(&quot;=============&quot;);\n        System.out.print(&quot;Vorher: &quot;);\n        this.OutputOfIntArray(myArray);\n\n        long startTime = System.nanoTime();\n        this.sort(myArray, false);\n        long endTime = System.nanoTime();\n\n        System.out.print(&quot;Nachher: &quot;);\n        this.OutputOfIntArray(myArray);\n\n        System.out.println(&quot;Ich habe &quot; + (endTime-startTime) + &quot; ns mit einem Array von &quot; + myArray.length + &quot; und einem Wertebereich\/Histogramm von &quot; + Arrays.stream(myArray).max().getAsInt() + &quot; Zahlen gebraucht! \\n\\n&quot;);\n\n        System.out.println(&quot;Gro\u00dfes Array, kleiner Wertebereich&quot;);\n        System.out.println(&quot;==================================&quot;);\n        System.out.print(&quot;Vorher: &quot;);\n        int&#x5B;] grossesArray = this.generateIntegerArrayOfSize(10000000, 100000);\n\n        startTime = System.nanoTime();\n        this.sort(grossesArray, false);\n        endTime = System.nanoTime();\n\n        System.out.println(&quot;Ich habe &quot; + (endTime-startTime) + &quot; ns mit einem Array von &quot; + grossesArray.length + &quot; und einem Wertebereich\/Histogramm von &quot; + Arrays.stream(grossesArray).max().getAsInt() + &quot; Zahlen gebraucht! \\n\\n&quot;);\n\n        System.out.println(&quot;Kleines Array, gro\u00dfer Wertebereich&quot;);\n        System.out.println(&quot;==================================&quot;);\n        System.out.print(&quot;Vorher: &quot;);\n        int&#x5B;] kleinesArray = this.generateIntegerArrayOfSize(100000, 10000000);\n\n        startTime = System.nanoTime();\n        this.sort(kleinesArray, false);\n        endTime = System.nanoTime();\n\n        System.out.println(&quot;Ich habe &quot; + (endTime-startTime) + &quot; ns mit einem Array von &quot; + kleinesArray.length + &quot; und einem Wertebereich\/Histogramm von &quot; + Arrays.stream(kleinesArray).max().getAsInt() + &quot; Zahlen gebraucht! \\n\\n&quot;);\n    }\n\n    public void sort(int&#x5B;] myArray) \n    {\n        this.sort(myArray, true);\n    }\n\n    public void sort(int&#x5B;] myArray, boolean verbose) \n    {\n        \/\/int maxValue = findMax(elements);\n        int maxValue = Arrays.stream(myArray).max().getAsInt();\n        int&#x5B;] counts = new int&#x5B;maxValue + 1];\n\n        \/\/ Phase 1: Erstelle das Histogramm\n        for (int element : myArray) \n        {\n            counts&#x5B;element]++;\n        }\n\n        if (verbose)\n        {\n            System.out.println(&quot;Erstelle Histogramm als Array mit den H\u00e4ufigkeiten der Zahlen im Array&quot;);\n        \n            \/\/ Optional - kann auskommentiert werden: Headline von Histogramm und Ausgabe Histogramm\n            for (int i = 0; i &lt; maxValue; i++)\n            {\n                System.out.print(i);\n\n                if (i + 1 != maxValue)\n                {\n                    System.out.print(&quot;;&quot;);\n                }\n            }\n\n            System.out.println(&quot;&quot;);\n            this.OutputOfIntArray(counts);\n        }\n\n        \/\/ Phase 2: Aggregiere die Zahlen, um die Startadressen in Zielarray zu ermitteln\n        for (int i = 1; i &lt;= maxValue; i++) \n        {\n            \/\/ Die Daten im Array werden von links nach rechts kummuliert\n            \/\/ um die Startadresse f\u00fcr jede Zahl zu bekommen.\n            counts&#x5B;i] += counts&#x5B;i - 1];\n        }\n\n        if (verbose)\n        {\n            System.out.println(&quot;Array mit den aggregierten Zahlen (Histogramm) f\u00fcr die Startadresse im Zielarray:&quot;);\n            this.OutputOfIntArray(counts);\n        }\n\n        \/\/ Phase 3: Schreibe die Zahlen ins Zielarray\n        int&#x5B;] target = new int&#x5B;myArray.length];\n\n        for (int i = myArray.length - 1; i &gt;= 0; i--) \n        {\n            int element = myArray&#x5B;i];\n            \n            counts&#x5B;element] = counts&#x5B;element] - 1;\n\n            if (verbose)\n            {\n                System.out.println(&quot;Schreibe &quot; + element +&quot; an Index &quot; + counts&#x5B;element] + &quot; des zu sortierten Arrays!&quot;);\n            }\n\n            target&#x5B;counts&#x5B;element]] = element;\n        }\n\n        \/\/ Copy target back to input array\n        System.arraycopy(target, 0, myArray, 0, myArray.length);\n    } \n\n    public static void main(String&#x5B;] args) \n    {\n        \/\/ Instanziere aus den statischem Programm ein echtes Objekt\n        \/\/ damit nicht alle Methoden und Variablen static sein m\u00fcssen.\n        program = new CountingSort();\n    }\n}\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Ausgabe<\/h2>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\nKleines Array\n=============\nVorher: 22;6;2;4;10;3;9;7;5;8;1\nNachher: 1;2;3;4;5;6;7;8;9;10;22\nIch habe 12449300 ns mit einem Array von 11 und einem Wertebereich\/Histogramm von 22 Zahlen gebraucht! \n\n\nGro\u00dfes Array, kleiner Wertebereich (Ausgabe aus)\n================================================\nIch habe 75933500 ns mit einem Array von 10000000 und einem Wertebereich\/Histogramm von 99999 Zahlen gebraucht! \n\n\nKleines Array, gro\u00dfer Wertebereich (Ausgabe aus)\n================================================\nIch habe 25634500 ns mit einem Array von 100000 und einem Wertebereich\/Histogramm von 9999905 Zahlen gebraucht! \n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Komplexit\u00e4t: O-Notation (Ordnung)<\/h2>\n\n\n\n<p>Die Laufzeit der Funktion h\u00e4ngt von\u00a0<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/a601995d55609f2d9f5e233e36fbe9ea26011b3b\" alt=\"{\\displaystyle n}\">\u00a0(Anzahl der Elemente des Eingabearrays) und\u00a0<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c3c9a2c7b599b37105512c5d570edc034056dd40\" alt=\"{\\displaystyle k}\">\u00a0(die Gr\u00f6\u00dfe des Zahlenintervalls) ab. Die\u00a0for-Schleifen\u00a0werden jeweils\u00a0<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/a601995d55609f2d9f5e233e36fbe9ea26011b3b\" alt=\"{\\displaystyle n}\">-mal oder\u00a0<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/c3c9a2c7b599b37105512c5d570edc034056dd40\" alt=\"{\\displaystyle k}\">-mal durchlaufen. Die\u00a0Zeitkomplexit\u00e4t\u00a0von Countingsort betr\u00e4gt somit\u00a0<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/b27028c996fca9e2546dd7e6af85169438cc479d\" alt=\"{\\displaystyle {\\mathcal {O}}(n+k)}\">.<\/p>\n\n\n\n<p><\/p>\n<iframe src=\"http:\/\/www.facebook.com\/plugins\/like.php?href=https%3A%2F%2Fwww.capri-soft.de%2Fblog%2F%3Fp%3D4061&amp;layout=standard&amp;show_faces=true&amp;width=450&amp;action=like&amp;colorscheme=light\" scrolling=\"no\" frameborder=\"0\" allowTransparency=\"true\" style=\"border:none; overflow:hidden; width:450px;margin-top:5px;\"><\/iframe>","protected":false},"excerpt":{"rendered":"<p>Der Algorithmus Der Counting Sort ist ein Out-of-place-Sortieralgorithmus, da er das zu sortierende Array im Gegensatz zu Quick Sort oder Bubble Sort nicht direkt sortiert, sondern vorher eine Speicherkopie anlegt, die im Abschluss auf das zu sortierende Array kopiert wird. Der Algorithmus ist genau dann effizient, wenn man viele (doppelte) Zahlen in einem kleinem Wertebereich &hellip; <a href=\"https:\/\/www.capri-soft.de\/blog\/?p=4061\" class=\"more-link\"><span class=\"screen-reader-text\">Algorithmen und Datenstrukturen: Der Counting Sort in Java<\/span> weiterlesen <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[475,15,3],"tags":[454,500,499,502,457,476,477,501,461,462],"class_list":["post-4061","post","type-post","status-publish","format-standard","hentry","category-algorithmen-und-datenstrukturen","category-java","category-programmierung","tag-algodat","tag-counting-sort-2","tag-counting-sort","tag-countingsort","tag-java","tag-komplexitaet","tag-laufzeit","tag-laufzeitkomplexitaet","tag-sortieralgorithmus","tag-sortieren"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p4yGeN-13v","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4061","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4061"}],"version-history":[{"count":1,"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4061\/revisions"}],"predecessor-version":[{"id":4062,"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4061\/revisions\/4062"}],"wp:attachment":[{"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4061"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4061"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.capri-soft.de\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4061"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}