{"id":12211,"date":"2020-07-08T09:00:00","date_gmt":"2020-07-08T07:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=12211"},"modified":"2025-12-04T12:03:19","modified_gmt":"2025-12-04T11:03:19","slug":"bubble-sort","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/bubble-sort\/","title":{"rendered":"Bubble Sort \u2013 Algorithmus, Quellcode, Zeitkomplexit\u00e4t"},"content":{"rendered":"\n<p>Dieser Artikel ist Teil der Serie <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/sortieralgorithmen\/\">\u201eSortieralgorithmen: Ultimate Guide\u201c<\/a>&nbsp;und\u2026<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>erkl\u00e4rt die Funktionsweise von Bubble Sort,<\/li>\n\n\n\n<li>stellt den Quellcode von Bubble Sort vor,<\/li>\n\n\n\n<li>erkl\u00e4rt, wie man die Zeitkomplexit\u00e4t von Bubble Sort herleitet<\/li>\n\n\n\n<li>und pr\u00fcft, ob die Performance der eigenen Implementierung dem entsprechend der Zeitkomplexit\u00e4t erwarteten Laufzeitverhalten entspricht.<\/li>\n<\/ul>\n\n\n\n<p>Die Quellcodes aller Artikel dieser Serie findest du in meinem&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\" target=\"_blank\">GitHub-Repository<\/a>.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe title=\"Bubble Sort Algorithmus [mit Animation, Deutsch]\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/Mj-payJDsdw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bubble-sort-algorithmus\">Bubble Sort Algorithmus<\/h2>\n\n\n\n<p>Bei Bubble Sort (auch: \"Bubblesort\") werden jeweils zwei aufeinanderfolgende Elemente miteinander verglichen und \u2013 wenn das linke Element gr\u00f6\u00dfer ist als das rechte \u2013 werden diese vertauscht. <\/p>\n\n\n\n<p>Diese Vergleichs- und Tauschoperationen f\u00fchrt man von links nach rechts \u00fcber alle Elemente durch, so dass nach dem ersten Durchlauf das gr\u00f6\u00dfte Element ganz rechts positioniert ist (besser gesagt: <em>sp\u00e4testens<\/em> nach dem ersten Durchlauf \u2013 es kann auch schon vorher dort angekommen sein).<\/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\" nowprocket><\/script><\/div>\n\n\n\n<p>Diesen Prozess wiederholt man solange, bis es in einem Durchlauf zu keinem weiteren Vertauschen mehr kommt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bubble-sort-beispiel\">Bubble Sort Beispiel<\/h3>\n\n\n\n<p>Im folgenden zeige ich, wie man das Array [6, 2, 4, 9, 3, 7] mit Bubble Sort  sortiert:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Vorbereitung<\/h4>\n\n\n\n<p>Wir teilen das Array gedanklich in einen linken, nicht sortierten, und einen rechten, sortierten Teil. Der rechte Teil ist zu Beginn leer:<\/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=\"1158\" height=\"800\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0.png\" alt=\"Bubble Sort Algorithmus - Vorbereitung\" class=\"wp-image-14430\" style=\"width:579px;height:400px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-224x155.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-336x232.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-504x348.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-672x464.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-400x276.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-600x415.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-800x553.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithmus_schritt0-944x652.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Iteration 1<\/h4>\n\n\n\n<p>Wir vergleichen die ersten beiden Elemente, die 6 und die 2. Da die 6 kleiner ist, vertauschen wir die Elemente:<\/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=\"1162\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 1\" class=\"wp-image-14432\" style=\"width:581px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-224x147.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-336x220.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-504x330.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-672x440.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-400x262.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-600x392.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-800x523.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_algorithm_step1-944x617.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>Nun vergleichen wir das zweite mit dem dritten Element, also die 6 mit der 4. Auch diese liegen in verkehrter Reihenfolge vor und werden vertauscht:<\/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=\"1162\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 2\" class=\"wp-image-14436\" style=\"width:581px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-224x147.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-336x220.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-504x330.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-672x440.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-400x262.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-600x392.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-800x523.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step2-944x617.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>Wir vergleichen das dritte mit dem vierten Element, also die 6 mit der 9. Die 6 ist kleiner als die 9, also brauchen wir diese zwei Elemente nicht zu vertauschen.<\/p>\n\n\n\n<p>Das vierte und f\u00fcnfte Element, die 9 und die 3, m\u00fcssen wiederum vertauscht werden:<\/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=\"1162\" height=\"786\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 3\" class=\"wp-image-14437\" style=\"width:581px;height:393px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-224x152.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-336x227.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-504x341.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-672x455.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-400x271.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-600x406.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-800x541.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step3-944x639.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>Und zuletzt m\u00fcssen das f\u00fcnfte und sechste Elemente, die 9 und die 7, miteinander vertauscht werden. Danach ist die erste Iteration abgeschlossen.<\/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=\"1162\" height=\"786\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 4\" class=\"wp-image-14438\" style=\"width:581px;height:393px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-224x152.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-336x227.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-504x341.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-672x455.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-400x271.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-600x406.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-800x541.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step4-944x639.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>Die 9 hat ihre finale Position erreicht und wir verschieben die Grenze zwischen den Bereichen um eine Position nach links:<\/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=\"1158\" height=\"732\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 5\" class=\"wp-image-14439\" style=\"width:579px;height:366px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-224x142.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-336x212.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-504x319.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-672x425.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-400x253.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-600x379.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-800x506.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step5-944x597.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<p>Diese Bereichsgrenze zeigt uns in der n\u00e4chsten Iteration, bis zu welcher Position die Elemente vergleichen werden m\u00fcssen. Die Bereichsgrenze gibt es \u00fcbrigens nur in der optimierten Variante von Bubble Sort. In der urspr\u00fcnglichen Variante fehlt sie, so dass in jeder Iteration unn\u00f6tigerweise bis zum Ende des Arrays verglichen wird.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Iteration 2<\/h4>\n\n\n\n<p>Wir starten erneut am Anfang des Arrays und vergleichen die 2 mit der 4. Diese liegen in korrekter Reihenfolge vor und m\u00fcssen nicht vertauscht werden.<\/p>\n\n\n\n<p>Das gleiche gilt f\u00fcr die 4 und die 6.<\/p>\n\n\n\n<p>Die 6 und die 3 hingegen m\u00fcssen vertauscht werden, um in richtiger Reihenfolge vorzuliegen:<\/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=\"1158\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 6\" class=\"wp-image-14440\" style=\"width:579px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-224x147.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-336x221.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-504x331.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-672x441.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-400x263.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-600x394.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-800x525.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step6-944x620.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<p>Die 6 und die 7 liegen in korrekter Reihenfolge vor und m\u00fcssen nicht vertauscht werden. Weiter brauchen wir nicht zu vergleichen, denn die 9 liegt bereits im sortierten Bereich.<\/p>\n\n\n\n<p>Zuletzt schieben wir die Bereichsgrenze wieder um eine Position nach links, damit wir die letzten zwei Elemente, die 7 und die 9, nicht weiter betrachten m\u00fcssen.<\/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=\"1158\" height=\"732\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 7\" class=\"wp-image-14441\" style=\"width:579px;height:366px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-224x142.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-336x212.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-504x319.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-672x425.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-400x253.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-600x379.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-800x506.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step7-944x597.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Iteration 3<\/h4>\n\n\n\n<p>Wieder starten wir am Anfang des Arrays. Die 2 und die 4 stehen korrekt zueinander. Die 4 und die 3 m\u00fcssen vertauscht werden:<\/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=\"1158\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 8\" class=\"wp-image-14444\" style=\"width:579px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-224x147.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-336x221.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-504x331.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-672x441.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-400x263.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-600x394.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-800x525.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step8-944x620.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<p>Die 4 und die 6 m\u00fcssen nicht vertauscht werden. Die 7 und die 9 sind bereits sortiert. Damit ist diese Iteration auch schon beendet und wir schieben die Bereichsgrenze nach links:<\/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=\"1158\" height=\"732\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 9\" class=\"wp-image-14445\" style=\"width:579px;height:366px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-224x142.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-336x212.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-504x319.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-672x425.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-400x253.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-600x379.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-800x506.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step9-944x597.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Iteration 4<\/h4>\n\n\n\n<p>Wir beginnen wieder am Anfang des Arrays. Im unsortierten Bereich m\u00fcssen weder die 2 und 3 noch die 3 und 4 vertauscht werden. Damit sind alle Elemente sortiert und wir k\u00f6nnen den Algorithmus beenden.<\/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=\"1158\" height=\"732\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10.png\" alt=\"Bubble Sort Algorithmus - Iteration 1, Schritt 10\" class=\"wp-image-14446\" style=\"width:579px;height:366px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-224x142.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-336x212.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-504x319.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-672x425.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-400x253.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-600x379.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-800x506.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_algorithm_step10-944x597.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"herkunft-des-namens\">Herkunft des Namens<\/h3>\n\n\n\n<p>Wenn wir die Vertauschoperationen des vorherigen Beispiels animieren, steigen die Elemente nach und nach bis zu ihren Zielpositionen auf \u2013 \u00e4hnlich wie Luftblasen (english: \"bubbles\"), daher der Name \"Bubble Sort\":<\/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=\"502\" height=\"732\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_animated.gif\" alt=\"Bubble Sort Algorithmus - Animation\" class=\"wp-image-14428\" style=\"width:251px;height:366px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_animated.gif 502w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_animated-224x327.gif 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_animated-336x490.gif 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/bubble_sort_animated-400x583.gif 400w\" sizes=\"(max-width: 502px) 100vw, 502px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bubble-sort-java-quellcode\">Bubble Sort Java Quellcode<\/h2>\n\n\n\n<p>Im folgenden findest Du die oben beschriebene, optimierte Implementierung von Bubble Sort.<\/p>\n\n\n\n<p>Da in der ersten Iteration das gr\u00f6\u00dfte Element bis ganz nach rechts wandert, in der zweiten Iteration das zweitg\u00f6\u00dfte bis zur zweitletzten Position, usw., m\u00fcssen wir in jeder Iteration ein Element weniger vergleichen als in der vorherigen. <\/p>\n\n\n\n<p>(Im Beispiel im vorangegangenen Abschnitt hatte ich das durch die Bereichsgrenze dargestellt, die nach jeder Iteration um eine Position nach links wandert.)<\/p>\n\n\n\n<p>Dazu dekrementieren wir in der \u00e4u\u00dferen Schleife den Wert <code>max<\/code>, beginnend bei <code>elements.length - 1<\/code>, in jeder Iteration um eins.<\/p>\n\n\n\n<p>Die innere Schleife vergleicht dann jeweils zwei Elemente bis zur Position <code>max<\/code> miteinander und vertauscht diese, wenn das linke Element gr\u00f6\u00dfer ist als das rechte.<\/p>\n\n\n\n<p>Wurden in einer Iteration keine Elemente vertauscht (d. h. <code>swapped<\/code> ist <code>false<\/code>), endet der Algorithmus vorzeitig.<\/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\">BubbleSortOpt1<\/span> <\/span>{\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/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\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> max = elements.length - <span class=\"hljs-number\">1<\/span>; max &gt; <span class=\"hljs-number\">0<\/span>; max--) {\n      <span class=\"hljs-keyword\">boolean<\/span> swapped = <span class=\"hljs-keyword\">false<\/span>;\n      <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; max; i++) {\n        <span class=\"hljs-keyword\">int<\/span> left = elements&#091;i];\n        <span class=\"hljs-keyword\">int<\/span> right = elements&#091;i + <span class=\"hljs-number\">1<\/span>];\n        <span class=\"hljs-keyword\">if<\/span> (left &gt; right) {\n          elements&#091;i + <span class=\"hljs-number\">1<\/span>] = left;\n          elements&#091;i] = right;\n          swapped = <span class=\"hljs-keyword\">true<\/span>;\n        }\n      }\n      <span class=\"hljs-keyword\">if<\/span> (!swapped) <span class=\"hljs-keyword\">break<\/span>;\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>Der abgebildete Code unterscheidet sich leicht von der Klasse&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/bubblesort\/BubbleSortOpt1.java\" target=\"_blank\">BubbleSortOpt1 im GitHub-Repository<\/a>: Diese implementiert das&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/SortAlgorithm.java\" target=\"_blank\">Interface SortAlgorithm<\/a>, um innerhalb des Testframeworks austauschbar zu sein.<\/p>\n\n\n\n<p>Die nicht-optimierte Variante \u2013 in der der Algorithmus in jeder Iteration alle Elemente bis zum Ende vergleicht \u2013 findest du in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/bubblesort\/BubbleSort.java\" target=\"_blank\">BubbleSort<\/a>.<\/p>\n\n\n\n<p>In der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/bubblesort\/BubbleSortOpt2.java\" target=\"_blank\">BubbleSortOpt2<\/a> findest du einen <em>theoretisch<\/em> noch st\u00e4rker optimierten Algorithmus. Es kann n\u00e4mlich auch sein, dass nach der <em>n<\/em>-ten Iteration, nicht nur die letzten <em>n<\/em> Elemente sortiert sind, sondern mehr \u2013 je nachdem, wie die Elemente urspr\u00fcnglich angeordnet waren. <\/p>\n\n\n\n<p>Diese Variante z\u00e4hlt daher <code>max<\/code> nicht um jeweils 1 herunter, sondern setzt <code>max<\/code> nach jeder Iteration auf die Position desjenigen Elements, das zuletzt vertauscht wurde. Der Test <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/comparisons\/CompareBubbleSorts.java\" target=\"_blank\">CompareBubbleSorts<\/a> zeigt allerdings, dass diese Variante in der Praxis langsamer ist:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">----- Results after 50 iterations-----\nBubbleSort     -&gt; fastest: 772.6 ms, median: 790.3 ms\nBubbleSortOpt1 -&gt; fastest: 443.2 ms, median: 452.7 ms\nBubbleSortOpt2 -&gt; fastest: 497.0 ms, median: 510.0 ms <\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die vollst\u00e4ndige Ausgabe des Testprogramms findest Du in der Datei <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-07-02\/TestResults_BubbleSort_Algorithms.log\" target=\"_blank\">TestResults_BubbleSort_Algorithms.log<\/a>.<\/p>\n\n\n\n<p>Warum ist die zweite optimierte Variante langsamer? Meine Vermutung ist, dass das Speichern und das (innerhalb einer Iteration) mehrfache Aktualisieren der Position des zuletzt vertauschten Elements deutlich teurer ist als das (pro Iteration) maximal einmalige \u00c4ndern des <code>swapped<\/code>-Werts.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bubble-sort-zeitkomplexitaet\">Bubble Sort Zeitkomplexit\u00e4t<\/h2>\n\n\n\n<p>Wir bezeichnen die Anzahl der zu sortierenden Elemente mit&nbsp;<em>n<\/em>, im Beispiel oben w\u00e4re&nbsp;<em>n = 6<\/em>.<\/p>\n\n\n\n<p>Die zwei ineinander verschachtelten Schleifen lassen vermuten, dass wir es bei Bubble Sort mit quadratischem Aufwand zu tun haben, also einer Zeitkomplexit\u00e4t* von <em>O(n\u00b2)<\/em>. Dies w\u00e4re dann der Fall, wenn beide Schleifen bis zu einem Wert iteratieren, der linear mit <em>n<\/em> steigt.<\/p>\n\n\n\n<p>Dies ist bei Bubble Sort nicht ganz so einfach nachzuweisen, wie z. B. bei <a href=\"\/de\/algorithmen\/insertion-sort\/#Insertion_Sort_Zeitkomplexitaet\">Insertion Sort<\/a> oder <a href=\"\/de\/algorithmen\/selection-sort\/#Selection_Sort_Zeitkomplexitaet\">Selection Sort<\/a>. <\/p>\n\n\n\n<p>Bei Bubble Sort m\u00fcssen wir <em>best<\/em>, <em>worse<\/em> und <em>average case<\/em> separat betrachten. Dies geschieht in den folgenden Unterabschnitten.<\/p>\n\n\n\n<p class=\"hc-footnote has-very-light-gray-background-color has-background\">* Die Begriffe \u201eZeitkomplexit\u00e4t\u201c und \u201eO-Notation\u201c (ausgesprochen \u201eGro\u00df O-Notation\u201c) erkl\u00e4re ich&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">in diesem Artikel<\/a>&nbsp;anhand von Beispielen und Diagrammen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-im-best-case\">Zeitkomplexit\u00e4t im best case<\/h3>\n\n\n\n<p>Fangen wir mit dem einfachsten Fall an: Falls die Zahlen bereits aufsteigend sortiert sind, wird der Algorithmus in der ersten Iteration feststellen, dass keine Zahlenpaare vertauscht werden m\u00fcssen und daraufhin umgehend terminieren.<\/p>\n\n\n\n<p>Dabei muss der Algorithmus <em>n-1<\/em> Vergleiche durchf\u00fchren; also gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Bubble Sort betr\u00e4gt im&nbsp;<em>best case<\/em>:&nbsp;<em>O(n)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-im-worst-case\">Zeitkomplexit\u00e4t im worst case<\/h3>\n\n\n\n<p>Den worst case demonstriere ich an einem Beispiel. Nehmen wir an, wir wollen das absteigend sortierte Array [6, 5, 4, 3, 2, 1] mit Bubble Sort sortieren.<\/p>\n\n\n\n<p>In der ersten Iteration wandert das gr\u00f6\u00dfte Element, die 6, von ganz links nach ganz rechts. Die f\u00fcnf Einzelschritte (Vertauschen der Paare 6\/5, 6\/4, 6\/3, 6\/2, 6\/1) habe ich in der Abbildung weggelassen:<\/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=\"1162\" height=\"558\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1.png\" alt=\"Bubble Sort - Zeitkomplexit\u00e4t im worst case - Schritt 1\" class=\"wp-image-14517\" style=\"width:581px;height:279px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-224x108.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-336x161.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-504x242.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-672x323.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-400x192.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-600x288.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-800x384.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step1-944x453.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>In der zweiten Iteration wird das zweitgr\u00f6\u00dfte Element, die 5, von ganz links \u2013 \u00fcber vier Zwischenschritte \u2013 an die vorletzte Position verschoben:<\/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=\"1162\" height=\"554\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2.png\" alt=\"Bubble Sort - Zeitkomplexit\u00e4t im worst case - Schritt 2\" class=\"wp-image-14518\" style=\"width:581px;height:277px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-224x107.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-336x160.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-504x240.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-672x320.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-400x191.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-600x286.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-800x381.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step2-944x450.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>In der dritten Iteration wird die 4 \u2013 \u00fcber drei Zwischenschritte \u2013 an die drittletzte Stelle geschoben:<\/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=\"1162\" height=\"554\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3.png\" alt=\"Bubble Sort - Zeitkomplexit\u00e4t im worst case - Schritt 3\" class=\"wp-image-14519\" style=\"width:581px;height:277px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-224x107.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-336x160.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-504x240.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-672x320.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-400x191.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-600x286.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-800x381.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step3-944x450.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>In der vierten Iteration wird die 3 \u2013 \u00fcber zwei Einzelschritte \u2013 an ihre finale Position verschoben:<\/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=\"1162\" height=\"554\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4.png\" alt=\"Bubble Sort - Zeitkomplexit\u00e4t im worst case - Schritt 4\" class=\"wp-image-14520\" style=\"width:581px;height:277px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-224x107.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-336x160.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-504x240.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-672x320.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-400x191.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-600x286.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-800x381.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step4-944x450.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>Und zuletzt werden die 2 und die 1 vertauscht:<\/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=\"1162\" height=\"554\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5.png\" alt=\"Bubble Sort - Zeitkomplexit\u00e4t im worst case - Schritt 5\" class=\"wp-image-14521\" style=\"width:581px;height:277px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5.png 1162w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-224x107.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-336x160.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-504x240.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-672x320.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-400x191.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-600x286.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-800x381.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_worst_case_time_complexity_step5-944x450.png 944w\" sizes=\"(max-width: 1162px) 100vw, 1162px\" \/><\/figure>\n<\/div>\n\n\n<p>In Summe haben wir also 5 + 4 + 3 + 2 + 1 = 15 Vergleichs- und Tauschoperationen.<\/p>\n\n\n\n<p>Das k\u00f6nnen wir auch wie folgt ausrechnen:<\/p>\n\n\n\n<p>Sechs Elemente mal f\u00fcnf Vergleichs- und Tauschoperationen; geteilt durch zwei, da im Mittel \u00fcber alle Iterationen die H\u00e4lfte der Elemente verglichen und verschoben wird:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>6 \u00d7 5 \u00d7 \u00bd &nbsp; = &nbsp; 30 \u00d7 \u00bd &nbsp; = &nbsp; 15<\/em><\/p>\n\n\n\n<p>Ersetzen wir <em>6<\/em> durch <em>n<\/em>, erhalten wir:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>n \u00d7 (n \u2013 1) \u00d7 \u00bd<\/em><\/p>\n\n\n\n<p>Ausmultipliziert ergibt das:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>\u00bd&nbsp;(n\u00b2 \u2013 n)<\/em><\/p>\n\n\n\n<p>Die h\u00f6chste Potenz von <em>n<\/em> in diesem Term ist <em>n\u00b2<\/em>; es gilt also:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Bubble Sort betr\u00e4gt im&nbsp;<em>worst case<\/em>:&nbsp;<em>O(n\u00b2)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-im-average-case\">Zeitkomplexit\u00e4t im average case<\/h3>\n\n\n\n<p>Die durchschnittliche Zeitkomplexit\u00e4t l\u00e4sst sich bei Bubble Sort \u2013 im Gegensatz zu den meisten anderen Sortieralgorithmen \u2013 leider nicht auf anschauliche Art und Weise erkl\u00e4ren.<\/p>\n\n\n\n<p>Ohne dies mathematisch zu beweisen (das w\u00fcrde den Rahmen dieses Artikels sprengen) kann man grob sagen, dass man im <em>average case<\/em> etwa halb so viele Tauschoperationen hat wie im <em>worst case<\/em>, da sich etwa die H\u00e4lfte der Elemente im Vergleich zum Nachbarelement an der richtigen Position befindet. Die Anzahl der Tauschoperationen ist also:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>\u00bc&nbsp;(n\u00b2 \u2013 n)<\/em><\/p>\n\n\n\n<p>Bei der Anzahl der Vergleichsoperationen wird es noch komplizierter, diese betr\u00e4gt (Quelle: <a href=\"https:\/\/de.wikipedia.org\/wiki\/Bubblesort#Durchschnittlicher_Fall\" target=\"_blank\" rel=\"noopener\">Wikipedia<\/a>):<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>\u00bd (n\u00b2 - n \u00d7 ln(n) - (? + ln(2) - 1) \u00d7 n) + O(\u221an)<\/em><\/p>\n\n\n\n<p>In beiden Termen ist die h\u00f6chste Potenz von <em>n<\/em> wieder <em>n\u00b2<\/em>, so dass gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Bubble Sort betr\u00e4gt im&nbsp;<em>average case<\/em>:&nbsp;<em>O(n\u00b2)<\/em><\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-des-java-bubble-sort-beispiels\">Laufzeit des Java Bubble Sort-Beispiels<\/h2>\n\n\n\n<p>\u00dcberpr\u00fcfen wir die Theorie mit einem Test! Im GitHub-Repository findest du 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>, das Bubble Sort (und alle anderen in dieser Artikelserie vorgestellten Sortieralgorithmen) nach folgenden Kriterien testet:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>f\u00fcr Array-Gr\u00f6\u00dfen beginnend ab 1.024 Elementen, mit einer Verdoppelung nach jeder Iteration, bis entweder eine Array-Gr\u00f6\u00dfe von 536.870.912 erreicht ist (= 2<sup>29<\/sup>) oder ein Sortiervorgang l\u00e4nger als 20 Sekunden dauert;<\/li>\n\n\n\n<li>f\u00fcr unsortierte, aufsteigend und absteigend vorsortierte Elemente;<\/li>\n\n\n\n<li>mit zwei Warm-Up-Runden, um dem HotSpot-Compiler ausreichend Zeit zu geben, um den Code zu optimieren.<\/li>\n<\/ul>\n\n\n\n<p>Das ganze wird so oft wiederholt, bis der Prozess abgebrochen wird. Nach jeder Wiederholung gibt das Program den Median aller bisherigen Messergebnisse aus.<\/p>\n\n\n\n<p>Hier das Ergebnis f\u00fcr Bubble Sort nach 50 Iterationen:<\/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<\/th><th class=\"has-text-align-right\" data-align=\"right\">unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">absteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">aufsteigend<\/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\">8.192<\/td><td class=\"has-text-align-right\" data-align=\"right\">61,73 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">35,18 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,004 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.384<\/td><td class=\"has-text-align-right\" data-align=\"right\">294,64 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">141,16 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,008 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">32.768<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.272,07 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">566,39 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,015 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">65.536<\/td><td class=\"has-text-align-right\" data-align=\"right\">5.196,82 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.267,85 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,030 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">131.072<\/td><td class=\"has-text-align-right\" data-align=\"right\">20.903,54 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">9.068,25 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,060 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">262.144<\/td><td class=\"has-text-align-right\" data-align=\"right\"><em>\u2013<\/em><\/td><td class=\"has-text-align-right\" data-align=\"right\"><em>\u2013<\/em><\/td><td class=\"has-text-align-right\" data-align=\"right\">0,129 ms<\/td><\/tr><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\">536.870.912<\/td><td class=\"has-text-align-right\" data-align=\"right\"><em>\u2013<\/em><\/td><td class=\"has-text-align-right\" data-align=\"right\"><em>\u2013<\/em><\/td><td class=\"has-text-align-right\" data-align=\"right\">192,509 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Dies ist nur ein Auszug, das vollst\u00e4ndige Ergebnis findest Du <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-05-30\/Test_Results_Bubble_Sort.txt\" target=\"_blank\">hier<\/a>.<\/p>\n\n\n\n<p>Hier die Ergebnisse noch einmal als Diagramm:<\/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=\"1520\" height=\"797\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime.png\" alt=\"Bubble Sort Laufzeit im average, worst und best case\" class=\"wp-image-14513\" style=\"width:760px;height:399px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-224x117.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-336x176.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-504x264.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-672x352.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-400x210.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-600x315.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-800x419.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-944x495.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime-1200x629.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p>Bei aufsteigend vorsortierten Elementen ist Bubble Sort so schnell, dass die Kurve keinen Ausschlag nach oben zeigt. Deshalb ist hier die Kurve noch einmal einzeln:<\/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=\"1520\" height=\"797\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case.png\" alt=\"Bubble Sort Laufzeit im best case\" class=\"wp-image-14514\" style=\"width:760px;height:399px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-224x117.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-336x176.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-504x264.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-672x352.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-400x210.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-600x315.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-800x419.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-944x495.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Bubble_Sort_runtime_best_case-1200x629.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p>Es l\u00e4sst sich sehr gut erkennen, ...<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dass sich die Laufzeit bei Verdopplung der Eingabemenge bei unsortierten und absteigend sortierten Elementen in etwa vervierfacht;<\/li>\n\n\n\n<li>dass die Laufzeit bei aufsteigend sortierten Elementen linear w\u00e4chst und um Gr\u00f6\u00dfenordnungen kleiner ist als bei unsortierten Elementen;<\/li>\n\n\n\n<li>dass die Laufzeit im <em>average case<\/em> etwas mehr als doppelt so hoch ist wie im <em>worst case<\/em>.<\/li>\n<\/ul>\n\n\n\n<p>Die ersten zwei Beobachtungen entsprechen den Erwartungen.<\/p>\n\n\n\n<p>Doch warum ist die Laufzeit im <em>average case<\/em> so viel h\u00f6her als im <em>worst case<\/em>? M\u00fcssten wir dort nicht nur etwa halb so viele Tauschoperationen haben und zumindest minimal weniger Vergleiche \u2013 und dementsprechend eher die halbe Zeit als die doppelte?<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"tausch-und-vergleichsoperationen-im-average-und-worst-case\">Tausch- und Vergleichsoperationen im average und worst case<\/h3>\n\n\n\n<p>Um das zu pr\u00fcfen, nutze ich das Programm&nbsp;<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>, um die Anzahl der verschiedenen Operationen anzeigen zu lassen. Hier sind die Ergebnisse f\u00fcr unsortierte und absteigend sortierte Elemente in einer Tabelle zusammengefasst:<\/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<\/th><th class=\"has-text-align-right\" data-align=\"right\">Tauschen unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">Tauschen absteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">Vergleiche unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">Vergleiche 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><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">128<\/td><td class=\"has-text-align-right\" data-align=\"right\">8.050<\/td><td class=\"has-text-align-right\" data-align=\"right\">16.256<\/td><td class=\"has-text-align-right\" data-align=\"right\">8.136<\/td><td class=\"has-text-align-right\" data-align=\"right\">8.255<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">256<\/td><td class=\"has-text-align-right\" data-align=\"right\">31.854<\/td><td class=\"has-text-align-right\" data-align=\"right\">65.280<\/td><td class=\"has-text-align-right\" data-align=\"right\">32.893<\/td><td class=\"has-text-align-right\" data-align=\"right\">32.895<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">512<\/td><td class=\"has-text-align-right\" data-align=\"right\">128.340<\/td><td class=\"has-text-align-right\" data-align=\"right\">261.632<\/td><td class=\"has-text-align-right\" data-align=\"right\">130.767<\/td><td class=\"has-text-align-right\" data-align=\"right\">131.327<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">1.024<\/td><td class=\"has-text-align-right\" data-align=\"right\">528.004<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.047.552<\/td><td class=\"has-text-align-right\" data-align=\"right\">524.475<\/td><td class=\"has-text-align-right\" data-align=\"right\">524.799<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">2.048<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.111.760<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.192.256<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.097.546<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.098.175<\/td><\/tr><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><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Die Ergebnisse best\u00e4tigen die Annahme: Bei unsortierten Elementen haben wir etwa halb so viele Tauschoperationen und minimal weniger Vergleiche als bei absteigend sortierten Elementen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"warum-ist-bubble-sort-fuer-absteigend-sortierte-elemente-schneller-als-fuer-zufaellig-verteilte-elemente\">Warum ist Bubble Sort f\u00fcr absteigend sortierte Elemente schneller als f\u00fcr zuf\u00e4llig verteilte Elemente?<\/h3>\n\n\n\n<p>Wie kann es sein, dass Bubble Sort bei absteigend sortierten Element trotz doppelt so vieler Tauschoperationen so viel schneller ist als bei zuf\u00e4llig angeordneten Elementen?<\/p>\n\n\n\n<p>Die Ursache f\u00fcr diese Diskrepanz ist in der <a href=\"https:\/\/de.wikipedia.org\/wiki\/Sprungvorhersage\" target=\"_blank\" rel=\"noopener\">Sprungvorhersage<\/a> (englisch \"branch prediction\") zu finden:<\/p>\n\n\n\n<p>Wenn die Elemente absteigend sortiert sind, dann ist das Resultat der Vergleichsoperation <code>if (left &gt; right)<\/code> im unsortierten Bereich immer <code>true<\/code> und im sortierten Bereich immer <code>false<\/code>.<\/p>\n\n\n\n<p>Wenn die Sprungvorhersage davon ausgeht, dass das Ergebnis eines Vergleichs immer dasselbe ist wie das des vorangegangenen Vergleichs, dann hat sie mit dieser Annahme \u2013 mit einer einzigen Ausnahme: an der Bereichsgrenze \u2013 immer Recht. Somit kann die Befehls-Pipeline der CPU die meiste Zeit voll ausgenutzt werden.<\/p>\n\n\n\n<p>Bei unsortierten Daten hingegen k\u00f6nnen keine verl\u00e4sslichen Vorhersagen \u00fcber das Ergebnis des Vergleichs getroffen werden, so dass die Pipeline h\u00e4ufig gel\u00f6scht und neu gef\u00fcllt werden muss.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"weitere-eigenschaften-von-bubble-sort\">Weitere Eigenschaften von Bubble Sort<\/h2>\n\n\n\n<p>In diesem Abschnitt geht es um die Platzkomplexit\u00e4t, Stabilit\u00e4t und Parallelisierbarkeit von Bubble Sort.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"platzkomplexitaet-von-bubble-sort\">Platzkomplexit\u00e4t von Bubble Sort<\/h3>\n\n\n\n<p>Bubble Sort ben\u00f6tigt neben der Schleifenvariablen <code>max<\/code> und den Hilfsvariablen <code>swapped<\/code>, <code>left<\/code> und <code>right<\/code> keinen zus\u00e4tzlichen Speicherplatz.<\/p>\n\n\n\n<p>Die Platzkomplexit\u00e4t von Bubble Sort ist somit <em>O(1)<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stabilitaet-von-bubble-sort\">Stabilit\u00e4t von Bubble Sort<\/h3>\n\n\n\n<p>Dadurch, dass immer zwei nebeneinander liegende Elemente miteinander verglichen werden \u2013 und diese nur dann vertauscht werden, wenn das linke Element gr\u00f6\u00dfer ist als das rechte, k\u00f6nnen Elemente mit gleichem Key niemals die Position relativ zueinander tauschen.<\/p>\n\n\n\n<p>Dazu m\u00fcssten, wie beispielsweise bei Selection Sort, zwei Elemente \u00fcber mehr als eine Position hinweg ihre Pl\u00e4tze tauschen. Das kann hier nicht passieren.<\/p>\n\n\n\n<p>Bubble Sort ist somit ein stabiler Sortieralgorithmus.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"parallelisierbarkeit-von-bubble-sort\">Parallelisierbarkeit von Bubble Sort<\/h3>\n\n\n\n<p>Es gibt zwei Ans\u00e4tze, um Bubble Sort zu parallelisieren:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Ansatz 1 \"Odd-even sort\"<\/h4>\n\n\n\n<p>Man vergleicht parallel das erste mit dem zweiten Element, das dritte mit dem vierten, das f\u00fcnfte mit dem sechsten, usw. und vertauscht die jeweiligen Elemente, wenn das linke gr\u00f6\u00dfer ist als das rechte.<\/p>\n\n\n\n<p>Danach vergleicht man das zweite Element mit dem dritten, das vierte mit dem f\u00fcnften, das sechste mit dem siebten usw. <\/p>\n\n\n\n<p>Diese zwei Schritte f\u00fchrt man abwechselnd durch, solange bis in beiden Schritten keine Elemente mehr vertauscht werden:<\/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=\"1478\" height=\"1018\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even.png\" alt=\"Parallel sortieren mit Bubble Sort (odd-even)\" class=\"wp-image-14469\" style=\"width:739px;height:509px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even.png 1478w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-224x154.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-336x231.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-504x347.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-672x463.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-400x276.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-600x413.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-800x551.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-944x650.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_odd_even-1200x827.png 1200w\" sizes=\"(max-width: 1478px) 100vw, 1478px\" \/><\/figure>\n<\/div>\n\n\n<p>Diesen Algorithmus bezeichnet man auch als <a rel=\"noopener\" href=\"https:\/\/en.wikipedia.org\/wiki\/Odd%E2%80%93even_sort\" target=\"_blank\">\"Odd\u2013even sort\"<\/a>.<\/p>\n\n\n\n<p>Du findest den Quellcode in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/bubblesort\/BubbleSortParallelOddEven.java\" target=\"_blank\">BubbleSortParallelOddEven<\/a> im GitHub-Repository.<\/p>\n\n\n\n<p>Die Synchronisation zwischen den Schritten (die Threads d\u00fcrfen mit einem Schritt erst dann beginnen, wenn <em>alle<\/em> Threads den vorherigen Schritt beendet haben), erfolgt dabei mit einem <a rel=\"noopener\" href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/14\/docs\/api\/java.base\/java\/util\/concurrent\/Phaser.html\" target=\"_blank\">Phaser<\/a>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Ansatz 2 \"Divide and Conquer\"<\/h4>\n\n\n\n<p>Man teilt das zu sortierende Array in so viele Bereiche (\"Partitionen\"), wie man Cores zur Verf\u00fcgung hat.<\/p>\n\n\n\n<p>Nun f\u00fchrt man eine Bubble-Sort-Iteration in allen Partitionen parallel durch. Man wartet, bis alle Threads fertig sind, und vergleicht dann jeweils das letzte Element einer Partition mit dem ersten der n\u00e4chsten Partition. Wenn auch damit alle Threads fertig sind, beginnt der Vorgang von vorne.<\/p>\n\n\n\n<p>Diese Schritte wiederholt man solange, bis in allen Threads keine Elemente mehr vertauscht werden:<\/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=\"1478\" height=\"1018\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer.png\" alt=\"Parallel sortieren mit Bubble Sort (divide-and-conquer)\" class=\"wp-image-14471\" style=\"width:739px;height:509px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer.png 1478w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-224x154.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-336x231.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-504x347.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-672x463.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-400x276.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-600x413.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-800x551.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-944x650.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble_sort_parallel_divide_and_conquer-1200x827.png 1200w\" sizes=\"(max-width: 1478px) 100vw, 1478px\" \/><\/figure>\n<\/div>\n\n\n<p>Du findest den Quellcodes des Algorithmus in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/bubblesort\/BubbleSortParallelDivideAndConquer.java\">BubbleSortParallelDivideAndConquer<\/a> im GitHub-Repository.<\/p>\n\n\n\n<p>Auch hier wird zur Synchronisation der Threads ein Phaser verwendet. Tats\u00e4chlich ist ein Gro\u00dfteil des Codes beider Algorithmen gleich, da auch f\u00fcr den Odd-Even-Ansatz das Array in Partitionen aufgeteilt wird. Den gemeinsamen Code habe ich in die abstrakte Basisklasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/bubblesort\/BubbleSortParallel.java\" target=\"_blank\">BubbleSortParallelSort<\/a> verschoben.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Bubble Sort parallel: Performance<\/h4>\n\n\n\n<p>Die Performance der parallelen Varianten vergleiche ich mit dem oben bereits genannten Test <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/comparisons\/CompareBubbleSorts.java\" target=\"_blank\">CompareBubbleSorts<\/a>. Hier das Ergebnis f\u00fcr die parallelen Algorithmen, verglichen mit der schnellsten sequentiellen Variante:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">----- Results after 50 iterations-----\nBubbleSortOpt1                     -&gt; fastest:   443.2 ms, median:   452.7 ms\nBubbleSortParallelOddEven          -&gt; fastest:    62.6 ms, median:    68.6 ms\nBubbleSortParallelDivideAndConquer -&gt; fastest:   126.8 ms, median:   145.7 ms <\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die \"odd-even\"-Variante ist auf meiner 6-Core-CPU (12 virtuelle Kerne mit Hyper-Threading) und bei 20.000 unsortierten Elementen also 6,6 mal schneller als die sequentielle Variante.<\/p>\n\n\n\n<p>Der \"divide-and-conquer\"-Ansatz ist nur 3,1 mal schneller. Dies d\u00fcrfte daran liegen, dass jeder Thread im zweiten Teilschritt der Iteration jeweils nur einen Vergleich durchf\u00fchrt. Demgegen\u00fcber steht ein relativ hoher Synchronisationsaufwand durch den Phaser.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung\">Zusammenfassung<\/h2>\n\n\n\n<p>Bubble Sort ist ein einfach zu implementierender, stabiler Sortieralgorithmus mit einer Zeitkomplexit\u00e4t von <em>O(n\u00b2)<\/em> im <em>average<\/em> und <em>worst case<\/em> \u2013 und <em>O(n)<\/em> im <em>best case<\/em>.<\/p>\n\n\n\n<p>Weitere Sortieralgorithmen findest du in dieser&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/sortieralgorithmen\/#Vergleich_der_wichtigsten_Sortieralgorithmen\">\u00dcbersicht aller Sortieralgorithmen und ihrer Eigenschaften<\/a>&nbsp;im ersten Teil der Artikelserie.<\/p>\n\n\n\n<p>Bubble Sort war das letzte einfache Sortierverfahren dieser Artikelserie; im n\u00e4chsten Teil steigen wir mit <a href=\"\/de\/algorithmen\/quicksort\/\">Quicksort<\/a> in die effizienten Sortierverfahren ein.<\/p>\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>In diesem Artikel beschreibe ich, wie Bubble Sort funktioniert, stelle den Quellcode vor und erkl\u00e4re, wie man die Zeitkomplexit\u00e4t herleitet.<\/p>\n","protected":false},"author":1,"featured_media":43256,"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 Bubble Sort? Mit Illustrationen und Quellcode. Wie bestimmt man seine Zeitkomplexit\u00e4t (ohne komplizierte Mathematik)?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_metis_text_type":"standard","_metis_text_length":18220,"_post_count":0,"footnotes":""},"categories":[127],"tags":[129],"class_list":["post-12211","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\/07\/bubble-sort-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-sort-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/bubble-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":3,"uagb_excerpt":"In diesem Artikel beschreibe ich, wie Bubble Sort funktioniert, stelle den Quellcode vor und erkl\u00e4re, wie man die Zeitkomplexit\u00e4t herleitet.","public_identification_id":"8c5327e56f9e4c37908bff32e444b364","private_identification_id":"b1a3573abd5f4251be587581e65cc3d6","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12211","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=12211"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12211\/revisions"}],"predecessor-version":[{"id":54125,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12211\/revisions\/54125"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43256"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=12211"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=12211"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=12211"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}