{"id":4822,"date":"2024-07-08T12:37:46","date_gmt":"2024-07-08T12:37:46","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4822"},"modified":"2026-02-17T11:36:07","modified_gmt":"2026-02-17T11:36:07","slug":"counting-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/counting-sort\/","title":{"rendered":"Counting sort &#8211; Z\u00e4hlende Sortierung in Java"},"content":{"rendered":"<p><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\">Sortieralgorithmen<\/a> werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig f\u00fcr die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten ben\u00f6tigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus h\u00e4ngt von Faktoren wie der Gr\u00f6\u00dfe und den Eigenschaften der Eingabedaten, dem verf\u00fcgbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erkl\u00e4ren und sie in Java programmieren. Heute befassen wir uns mit der <strong>z\u00e4hlenden<\/strong> Sortierung. Bislang haben wir die folgenden Sortieralgorithmen behandelt:<\/p>\n<ul>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\">Sortieralgorithmen<\/a>: eine Einf\u00fchrung in das Sortieren von Daten,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bubble-sort\/\">Bubble sort<\/a> &#8211; Blasen-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/comb-sort\/\">Comb sort<\/a> &#8211; Kamm-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/big-o-notation\/\">Big O Notation<\/a>: Analyse der Komplexit\u00e4t von Algorithmen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\">Auswahlsortierung<\/a> &#8211; Sortieren nach Auswahl,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/insertion-sort\/\">Insertion sort<\/a> &#8211; Sortieren nach Einf\u00fcgung.<\/li>\n<\/ul>\n<h2>Counting sort<\/h2>\n<p>Bisher haben wir Algorithmen besprochen, die Elemente miteinander vergleichen und auf dieser Grundlage eine sortierte Ausgabe erzeugen. Heute stellen wir den ersten Algorithmus vor, der keinen Vergleich in seiner Grundlage verwendet. Counting Sort ist ein ganzzahliger stabiler Sortieralgorithmus, der auf dem Z\u00e4hlen von Objekten mit unterschiedlichen Schl\u00fcsselwerten basiert, aus denen die Position in der Ausgabereihenfolge bestimmt wird. Er ist nur in Situationen geeignet, in denen die Varianz der maximalen und minimalen Schl\u00fcsselwerte im Vergleich zur Anzahl der Elemente in der Eingabe relativ klein ist. Dieser Algorithmus wird oft als Hilfsroutine in der <strong>Radix-Variante<\/strong>verwendet.<\/p>\n<h2>Counting sort Algoritmus &#8211; Funktionsprinzip<\/h2>\n<p>Der Z\u00e4hlsortieralgorithmus ist geeignet, wenn wir viele Elemente mit ganzzahligen Schl\u00fcsseln haben, die sich idealerweise in einem relativ kleinen Bereich (max &#8211; min) wiederholen. Dann k\u00f6nnen wir diesen relativ effizienten Algorithmus zum Sortieren der Eingabeelemente verwenden. Er arbeitet nach dem Prinzip des Z\u00e4hlens des Auftretens jedes Schl\u00fcssels, den er in einem Hilfsarray speichert. Dieses wird dann in ein Array mit Indizes umgewandelt, die die Positionen der einzelnen Elemente enthalten. Es wird dann verwendet, um die Elemente aus dem Eingabevektor auf den Ausgabevektor abzubilden. Das Funktionsprinzip des Algorithmus l\u00e4sst sich am besten anhand eines praktischen Beispiels in Java verstehen, das wir implementieren werden.<\/p>\n<h2>Vorteile des Counting sort Algorithmus.<\/h2>\n<ul>\n<li>Einfach zu implementieren,<\/li>\n<li>Schnell und effizient, wenn der Wertebereich <strong>\ud835\udc58<\/strong> k im Vergleich zur Anzahl der Elemente im Eingang <strong>\ud835\udc5b<\/strong> n klein ist.<\/li>\n<li>stabil.<\/li>\n<\/ul>\n<h2>Nachteile des Counting sort Algorithmus<\/h2>\n<ul>\n<li>Funktioniert nur f\u00fcr Schl\u00fcssel mit ganzzahligen Werten,<\/li>\n<li>Ineffizient bei einem gro\u00dfen Wertebereich.<\/li>\n<\/ul>\n<h2>Counting sort Zeitintensit\u00e4t<\/h2>\n<table style=\"height: 72px\" width=\"496\">\n<thead>\n<tr style=\"height: 24px\">\n<th style=\"height: 48px;width: 103.537px\" rowspan=\"2\"><strong>Algorithmus<\/strong><\/th>\n<th style=\"height: 48px;width: 72.6875px\" rowspan=\"2\"><strong>Methode<\/strong><\/th>\n<th style=\"height: 24px;width: 300.138px\" colspan=\"3\"><strong>Zeitliche Komplexit\u00e4t<\/strong><\/th>\n<th style=\"height: 48px;width: 72.5625px\" rowspan=\"2\"><strong>Speicher<\/strong><\/th>\n<th style=\"height: 48px;width: 47.775px\" rowspan=\"2\"><strong>Stabil<\/strong><\/th>\n<\/tr>\n<tr style=\"height: 24px\">\n<th style=\"height: 24px;width: 100.838px\"><strong>schlechteste<\/strong><\/th>\n<th style=\"height: 24px;width: 136.675px\"><strong>durchschnittlich<\/strong><\/th>\n<th style=\"height: 24px;width: 52.225px\"><strong>beste<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr style=\"height: 24px\">\n<td style=\"height: 24px;width: 103.537px\">Counting sort<\/td>\n<td style=\"height: 24px;width: 72.6875px\">Z\u00e4hlen<\/td>\n<td style=\"height: 24px;width: 100.838px\">O(n+k)<\/td>\n<td style=\"height: 24px;width: 136.675px\">O(n+k)<\/td>\n<td style=\"height: 24px;width: 52.225px\">O(n+k)<\/td>\n<td style=\"height: 24px;width: 72.5625px\">O(k)<\/td>\n<td style=\"height: 24px;width: 47.775px\">Ja<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Die Variable k ist die Anzahl der Elemente des z\u00e4hlenden Hilfsarrays, mathematisch k = (Maximum &#8211; Minimum + 1). Da wir \u00fcber das Eingabe-Array der Elemente iterieren, erhalten wir eine zeitliche Komplexit\u00e4t von O(n). Die Iteration \u00fcber das Hilfs-Array tr\u00e4gt zu einer Komplexit\u00e4t von O(k) bei, so dass die gesamte zeitliche Komplexit\u00e4t insgesamt O(n+k) betr\u00e4gt. Die Speicherung von k Elementen im Hilfsarray im Speicher f\u00fchrt zu einer r\u00e4umlichen Komplexit\u00e4t von O(k).<\/p>\n<h2>Counting sort Animation, Visualisierung, gif<\/h2>\n<p>Die Visualisierung von Counting sort sieht wie folgt aus:<\/p>\n<figure id=\"attachment_3896\" aria-describedby=\"caption-attachment-3896\" style=\"width: 320px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-3894 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/Counting_Sort_Animation.gif\" alt=\"counting sort Visualisierung\" width=\"320\" height=\"320\" \/><figcaption id=\"caption-attachment-3896\" class=\"wp-caption-text\">SimonWaldherr, CC BY-SA 4.0, via Wikimedia Commons<\/figcaption><\/figure>\n<p style=\"text-align: center\"><em>Quelle : https:\/\/commons.wikimedia.org\/wiki\/Category:Animations_of_sort_algorithms<\/em><\/p>\n<p>Eine Animation des Counting Sort Algorithmus finden du zum Beispiel auf <a href=\"https:\/\/tobinatore.github.io\/algovis\/countingsort.html\" target=\"_blank\" rel=\"nofollow noopener\">diese Seite.<\/a><\/p>\n<h2>Counting sort Java-Implementierung<\/h2>\n<p>Jetzt zeigen wir eine einfache Implementierung des Counting Sort-Algorithmus in Java.<\/p>\n<p><strong><u>CountingSort.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">package sorting;\n\npublic class CountingSort {\n    private int min, max;\n\n    public void sort(int data[])\n    {\n        \/\/ Don&#039;t sort if there are no elements\n        if(data.length == 0)\n            return;\n\n        \/\/ Create ouput array\n        int[] output = new int[data.length];\n\n        \/\/ Find min and max value in 1 loop\n        min = data[0];\n        max = data[0];\n        for (int i = 1; i &lt; data.length; i++) {\n            if (data[i] &lt; min) {\n                min = data[i];\n            } else if (data[i] &gt; max) {\n                max = data[i];\n            }\n        }\n\n        \/\/ Create count array\n        int k = max - min + 1;\n        int[] count = new int[k];\n        System.out.println(&quot;min = &quot; + min + &quot;, max = &quot; + max +\n                &quot;, size (n) = &quot; + data.length + &quot;, range (k) = &quot; + k);\n\n        \/\/ Count occurrences of elements\n        for (int i = 0; i &lt; data.length; i++) {\n            count[data[i] - min]++;\n        }\n        System.out.print(&quot;Count array: &quot;);\n        printArray(count);\n\n        \/\/ Transform counts to positions\n        for (int i = 1; i &lt; count.length; i++) {\n            count[i] += count[i - 1];\n        }\n        System.out.print(&quot;Transformed count array: &quot;);\n        printArray(count);\n\n        \/\/ Map the elements from input to output based on count indexes\n        \/\/ Do it backwards\n        for (int i = data.length - 1; i &gt;= 0; i--) {\n            output[count[data[i] - min] - 1] = data[i];\n            count[data[i] - min]--;\n        }\n\n        \/\/ Copy the elements from output back to original array\n        for (int i = 0; i &lt; data.length; i++) {\n            data[i] = output[i];\n        }\n    }\n\n    \/\/ Function to print an array\n    public void printArray(int data[])\n    {\n        for (int i = 0; i &lt; data.length; i++)\n            System.out.print(data[i] + &quot; &quot;);\n        System.out.println();\n    }\n}<\/code><\/pre>\n<p>Der Algorithmus besteht aus den folgenden Schritten, die wir kurz erl\u00e4utern werden:<\/p>\n<h3>Leeres Feld pr\u00fcfen<\/h3>\n<p>Wenn das Feld leer ist, gibt es nichts zu sortieren.<\/p>\n<h3>Ermitteln der Minimal- und Maximalwerte<\/h3>\n<p>Zistime rozsah hodn\u00f4t min a max.<\/p>\n<h3>Erstellen und Initialisieren eines Z\u00e4hlarrays<\/h3>\n<p>Die Gr\u00f6\u00dfe des Z\u00e4hlfelds ist die Differenz zwischen dem H\u00f6chst- und dem Mindestwert plus eins, um den gesamten Wertebereich abzudecken.<\/p>\n<h3>Transformation in akkumulierte Summen<\/h3>\n<p>F\u00fcr jedes Element im Eingabefeld wird der Wert am entsprechenden Index im Z\u00e4hlfeld um eins erh\u00f6ht.<\/p>\n<h3>Umwandlung in kumulierte Z\u00e4hlungen<\/h3>\n<p>Jedes Element in der Z\u00e4hlmatrix wird durch die Summe aller vorherigen Werte aktualisiert, wodurch die endg\u00fcltigen Positionen der Elemente in der Ausgangsmatrix bestimmt werden.<\/p>\n<h3>Platzierung der Elemente im Ausgabefeld<\/h3>\n<p>Das Eingabe-Array wird r\u00fcckw\u00e4rts durchlaufen (um Stabilit\u00e4t zu gew\u00e4hrleisten) und die Elemente werden auf der Grundlage der Werte im Z\u00e4hl-Array im Ausgabe-Array platziert, wobei der Index des Z\u00e4hl-Arrays nach jeder Platzierung eines Elements um 1 verringert wird.<\/p>\n<h3>Kopieren der Ausgabe zur\u00fcck in das urspr\u00fcngliche Array<\/h3>\n<p>Die sortierten Elemente aus dem Ausgabefeld werden zur\u00fcck in das urspr\u00fcngliche Feld kopiert.<\/p>\n<p><strong><u>Main.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">import sorting.CountingSort;\n\npublic class Main {\n    public static void main(String[] args) {\n        int dataToSort[] = { 4, 2, 4, 2, 1, 1, 1, 7, 6, 3, 5, 5 };\n        CountingSort countingSort = new CountingSort();\n        System.out.print(&quot;Input: &quot;);\n        countingSort.printArray(dataToSort);\n        countingSort.sort(dataToSort);\n        System.out.print(&quot;Sorted: &quot;);\n        countingSort.printArray(dataToSort);\n    }\n}<\/code><\/pre>\n<p>Die Ausgabe dieses Beispiels ist:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-3890\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/triedenie-pocitanim-vystup-z-prikladu-790-390.webp\" alt=\"Ausgabe des Counting sort Beispiels\" width=\"600\" height=\"296\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/triedenie-pocitanim-vystup-z-prikladu-790-390.webp 790w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/triedenie-pocitanim-vystup-z-prikladu-790-390-300x148.webp 300w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/triedenie-pocitanim-vystup-z-prikladu-790-390-768x379.webp 768w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/p>\n<h2>Counting sort &#8211; Java-Code<\/h2>\n<p>Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausf\u00fchren kannst. Lade <a href=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/07\/CountingSort.zip\">den Java <strong>Counting Sort<\/strong> Code<\/a> herunter.<\/p>\n<p>Wenn du ein <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/java-entwickler-senior\/\">Java Programmierer<\/a> bist und nach Arbeit suchst, schau dir unsere <a href=\"https:\/\/msg-life.sk\/de\/mitarbeiter-benefits\/\">Mitareiterbenefits <\/a> an und reagiere auf die <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/\">neuesten Stellenangebote<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel erf\u00e4hrst du, was Counting sort ist, nach welchem Prinzip es funktioniert, welche Vorteile und Nachteile es hat und ein Beispiel f\u00fcr Java-Code.<\/p>\n","protected":false},"author":14,"featured_media":3886,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[48],"tags":[],"class_list":["post-4822","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4822","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/comments?post=4822"}],"version-history":[{"count":5,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4822\/revisions"}],"predecessor-version":[{"id":9716,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4822\/revisions\/9716"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media\/3886"}],"wp:attachment":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media?parent=4822"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/categories?post=4822"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/tags?post=4822"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}