{"id":4828,"date":"2024-08-23T15:50:53","date_gmt":"2024-08-23T15:50:53","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4828"},"modified":"2026-02-17T11:56:25","modified_gmt":"2026-02-17T11:56:25","slug":"bucket-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/bucket-sort\/","title":{"rendered":"Bucket sort (bin sort) &#8211; Sortieren nach Eimern (bins) in Java"},"content":{"rendered":"<p>Sortieralgorithmen 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 schnellen <strong>Bucket sort<\/strong>, auch bekannt als <strong>Bin-Sortierung<\/strong>. Bislang haben wir die folgenden Sortieralgorithmen behandelt:<\/p>\n<ul>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\" target=\"_blank\" rel=\"noopener\">Sortieralgorithmen<\/a>: eine Einf\u00fchrung in das Sortieren von Daten,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bubble-sort\/\" target=\"_blank\" rel=\"noopener\">Bubble sort<\/a> &#8211; Blasen-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/comb-sort\/\" target=\"_blank\" rel=\"noopener\">Comb sort<\/a> &#8211; Kamm-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/big-o-notation\/\" target=\"_blank\" rel=\"noopener\">Big O Notation<\/a>: Analyse der Komplexit\u00e4t von Algorithmen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\" target=\"_blank\" rel=\"noopener\">Selection sort<\/a> &#8211; Sortieren nach Auswahl,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/insertion-sort\/\" target=\"_blank\" rel=\"noopener\">Insertion sort<\/a> &#8211; Sortieren nach Einf\u00fcgung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/counting-sort\/\" target=\"_blank\" rel=\"noopener\">Counting sort<\/a> &#8211; Sortieren durch Z\u00e4hlen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/heap-sort\/\" target=\"_blank\" rel=\"noopener\">Heap sort<\/a> &#8211; Heap Sortierung<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/merge-sort\/\" target=\"_blank\" rel=\"noopener\">Merge sort<\/a> &#8211; Sortieren durch Aufteilen und Zusammenf\u00fchren,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/quick-sort\/\" target=\"_blank\" rel=\"noopener\">Quick sort <\/a> &#8211; schnelles Sortieren mit Pivot.<\/li>\n<\/ul>\n<h2>Bucket sort, Bin sort Algorithmus<\/h2>\n<p>Bucket (Bin) Sort ist eine spezielle Sortiertechnik, die darin besteht, die Elemente des Eingabevektors in verschiedene Gruppen (Buckets oder Bins) zu unterteilen. Diese Gruppen werden auf der Grundlage einer gleichm\u00e4\u00dfigen Verteilung gebildet (siehe auch <a href=\"https:\/\/www.investopedia.com\/terms\/u\/uniform-distribution.asp\" target=\"_blank\" rel=\"nofollow noopener\">Uniform distribution<\/a>). Die Gruppen werden dann einzeln durch einen beliebigen Sortieralgorithmus sortiert und die sortierte Ausgabe ist die Vereinigung der Ergebnisse der einzelnen Buckets. Die Rechenkomplexit\u00e4t des Algorithmus h\u00e4ngt dann von dem Algorithmus ab, der die Daten in jeder Gruppe sortiert, von der Anzahl der Gruppen sowie von der Gleichverteilung der Werte in der Eingabe.<\/p>\n<h2>Bucket sort, Bin sort &#8211; Funktionsprinzip des Algorithmus<\/h2>\n<p>Wenn wir eine gro\u00dfe Menge an Daten sortieren m\u00fcssen, die die Eigenschaft haben, gleichm\u00e4\u00dfig sortiert zu sein (z.B. Ordnungszahlen), k\u00f6nnen wir durch die Aufteilung in Untergruppen die Anzahl der Vergleiche zwischen den Elementen reduzieren, was uns hilft, die Sortierzeit zu verringern. Sobald die Daten sortiert sind, k\u00f6nnen wir sie in Gruppen sortiert lassen und beim Hinzuf\u00fcgen neuer Elemente zu den Gruppen nur die Gruppen sortieren, zu denen das neue Element hinzugef\u00fcgt wurde. Sortierte Daten lassen sich auch einfacher und schneller sortieren, wenn wir daf\u00fcr einen geeigneten Algorithmus verwenden, wie z.B. <a href=\"https:\/\/msgprogramator.sk\/de\/insertion-sort\/\" target=\"_blank\" rel=\"noopener\">Insertion sort<\/a>. Die Aufteilung in mehrere Gruppen erm\u00f6glicht es uns au\u00dferdem, parallele Sortier- und Datenverarbeitungstechniken einzusetzen. Das Grundprinzip des Bucket-Sortieralgorithmus ist wie folgt:<\/p>\n<ol start=\"1\">\n<li><strong>Bestimmung der Anzahl der Buckets<\/strong> Durch einen einmaligen Durchlauf der Werte k\u00f6nnen wir den maximalen Wert ermitteln.<\/li>\n<li><strong> Erstellung eines Arrays mit leeren Anfangs-Buckets<\/strong><\/li>\n<li><strong> Verteilung der Elemente in die entsprechenden Buckets<\/strong><br \/>\nAm besten erfolgt die Verteilung der Elemente (<strong><em>Scatter<\/em><\/strong>) mithilfe einer einfachen Hash-Funktion.<\/li>\n<li><strong> Sortierung der Elemente in jedem Bucket<\/strong><\/li>\n<li><strong> Zusammenf\u00fchren (<em>gather<\/em>) der Ergebnisse aus den einzelnen Buckets in der richtigen Reihenfolge<\/strong><\/li>\n<\/ol>\n<h2>Bucket sort Animation, Visualisierung<\/h2>\n<figure id=\"attachment_4213\" aria-describedby=\"caption-attachment-4213\" style=\"width: 890px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4211 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/bucket-sort-ilustracia-890-740.webp\" alt=\"Visuelle Darstellung des Bucket Sort-Algorithmus.\" width=\"890\" height=\"740\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/bucket-sort-ilustracia-890-740.webp 890w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/bucket-sort-ilustracia-890-740-300x249.webp 300w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/bucket-sort-ilustracia-890-740-768x639.webp 768w\" sizes=\"auto, (max-width: 890px) 100vw, 890px\" \/><figcaption id=\"caption-attachment-4213\" class=\"wp-caption-text\">Visuelle Darstellung des Bucket Sort-Algorithmus.<\/figcaption><\/figure>\n<h2>Vorteile des Bucket sort Algorithmus<\/h2>\n<ul>\n<li>Relativ effizient f\u00fcr Daten mit gleichm\u00e4\u00dfiger Verteilung: Dezimalzahlen im Bereich von 0,0 bis 1,0 oder Ganzzahlen in einem engen Bereich.<\/li>\n<li>Stabil, wenn ein stabiler Sortieralgorithmus zum Sortieren der Daten nach Gruppen verwendet wird.<\/li>\n<li>Es kann parallelisiert werden, um die Berechnungslast auf mehrere Prozessoren zu verteilen.<\/li>\n<\/ul>\n<h2>Nachteile des Bucket sort Algorithmus<\/h2>\n<ul>\n<li>Erfordert zus\u00e4tzlichen Speicherplatz f\u00fcr die Erstellung von Gruppen.<\/li>\n<li>Eine unpassend gew\u00e4hlte Varianzfunktion kann die Zeitkomplexit\u00e4t erheblich erh\u00f6hen.<\/li>\n<\/ul>\n<h2>Bucket Sort \u2013 Zeitkomplexit\u00e4t<\/h2>\n<table width=\"536\">\n<thead>\n<tr>\n<th rowspan=\"2\" width=\"94\"><strong>Algorithmus<\/strong><\/th>\n<th rowspan=\"2\" width=\"84\"><strong>Methode<\/strong><\/th>\n<th colspan=\"3\" width=\"208\"><strong>Zeitliche Komplexit\u00e4t<\/strong><\/th>\n<th rowspan=\"2\" width=\"82\"><strong>Speicher<\/strong><\/th>\n<th rowspan=\"2\" width=\"69\"><strong>Stabil<\/strong><\/th>\n<\/tr>\n<tr>\n<th width=\"73\"><strong>schlechteste<\/strong><\/th>\n<th width=\"63\"><strong>durchschnittlich<\/strong><\/th>\n<th width=\"71\"><strong>beste<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td width=\"94\">Bucket sort<\/td>\n<td width=\"84\">Distribution<\/td>\n<td width=\"73\">O(n\u00b2)<\/td>\n<td width=\"63\">O(n + k)<\/td>\n<td width=\"71\">O(n + k)<\/td>\n<td width=\"82\">O(n + k)<\/td>\n<td width=\"69\">ja\/nein<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Variable n = Anzahl der Array-Elemente, k = Anzahl der Eimer<\/p>\n<h3>Der schlimmste Fall von Bucket sort Zeitkomplexit\u00e4t<\/h3>\n<p>Im schlimmsten Fall landen alle Elemente im selben Bucket in umgekehrter Reihenfolge. Dies kann entweder auf eine ungeeignete Datenverteilung f\u00fcr diesen Algorithmus oder auf eine schlecht implementierte Streufunktion zur\u00fcckzuf\u00fchren sein. In diesem Fall n\u00e4hert sich die Zeitkomplexit\u00e4t O(n\u00b2).<\/p>\n<h2>Bucket Sort &#8211; Implementierung, Java-Code<\/h2>\n<p>Jetzt schauen wir uns die Implementierung des Bucket-Sort-Algorithmus in Java an.<\/p>\n<p><strong><u>BucketSort.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">package sorting;\n\nimport java.util.ArrayList;\nimport java.util.Collections;\n\npublic class BucketSort {\n    public void sort(float[] data)\n    {\n        \/\/ Set optimal bucket count here\n        int bucketCount = 10;\n        ArrayList&lt;Float&gt;[] buckets = new ArrayList[bucketCount];\n\n        \/\/ Create empty buckets\n        for (int i = 0; i &lt; bucketCount; i++) {\n            buckets[i] = new ArrayList&lt;&gt;();\n        }\n\n        \/\/ Scatter elements into buckets using appropriate hash function\n        for (float f : data) {\n            int bucketIndex = (int) Math.floor(f * 10);\n            buckets[bucketIndex].add(f);\n        }\n\n        System.out.println(&quot;After distribution:&quot;);\n        for (int i = 0; i &lt; bucketCount; i++) {\n            printBucket(i, buckets[i]);\n        }\n\n        \/\/ Sort all the buckets\n        for (int i = 0; i &lt; bucketCount; i++) {\n            Collections.sort(buckets[i]);\n        }\n\n        System.out.println(&quot;After sorting individual buckets:&quot;);\n        for (int i = 0; i &lt; bucketCount; i++) {\n            printBucket(i, buckets[i]);\n        }\n\n        \/\/ Concatenate buckets elements to get sorted data\n        int j = 0;\n        for (int i = 0; i &lt; bucketCount; i++) {\n            for (float num : buckets[i]) {\n                data[j++] = num;\n            }\n        }\n    }\n\n    public void printBucket(int id, ArrayList&lt;Float&gt; data)\n    {\n        System.out.println(&quot;Bucket &quot; + id + &quot; -&gt; &quot; + data);\n    }\n\n    \/\/ Function to print an array\n    public void printArray(float[] data)\n    {\n        for (int i = 0; i &lt; data.length; i++)\n            System.out.print(data[i] + &quot; &quot;);\n    }\n}<\/code><\/pre>\n<p><strong><u>Main.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">import sorting.BucketSort;\n\npublic class Main {\n    public static void main(String[] args) {\n        float[] dataToSort = { 0.88f, 0.16f, 0.39f, 0.26f, 0.82f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f };\n        BucketSort bucketSort = new BucketSort();\n        System.out.print(&quot;Input: &quot;);\n        bucketSort.printArray(dataToSort);\n        System.out.println();\n        bucketSort.sort(dataToSort);\n        System.out.print(&quot;Sorted: &quot;);\n        bucketSort.printArray(dataToSort);\n    }\n}<\/code><\/pre>\n<p>Die Ausgabe dieses Beispiels ist:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4220 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-bucket-sort-670-820.webp\" alt=\"Bucket Sort - Implementierung, Java-Code\" width=\"670\" height=\"820\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-bucket-sort-670-820.webp 670w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-bucket-sort-670-820-245x300.webp 245w\" sizes=\"auto, (max-width: 670px) 100vw, 670px\" \/><\/p>\n<p>Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausf\u00fchren kannst. Lade <a href=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/BucketSort.zip\" target=\"_blank\" rel=\"noopener\">den Java-Code f\u00fcr <strong>BucketSort<\/strong><\/a> herunter.<\/p>\n<p>Wenn du ein <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/java-entwickler-senior\/\" target=\"_blank\" rel=\"noopener\">Java Programmierer<\/a> bist und nach Arbeit suchst, schau dir unsere <a href=\"https:\/\/msg-life.sk\/de\/mitarbeiter-benefits\/\" target=\"_blank\" rel=\"noopener\">Mitareiterbenefits <\/a> an und reagiere auf die <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/\" target=\"_blank\" rel=\"noopener\">neuesten Stellenangebote<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Im Artikel erf\u00e4hrst du, was Bucket Sort ist, auf welchem Prinzip es basiert, seine Vor- und Nachteile, eine Visualisierung und ein Beispiel f\u00fcr Java-Code.<\/p>\n","protected":false},"author":14,"featured_media":4216,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[62,48],"tags":[],"class_list":["post-4828","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\/4828","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=4828"}],"version-history":[{"count":5,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4828\/revisions"}],"predecessor-version":[{"id":9740,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4828\/revisions\/9740"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media\/4216"}],"wp:attachment":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media?parent=4828"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/categories?post=4828"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/tags?post=4828"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}