{"id":4700,"date":"2024-05-13T15:40:06","date_gmt":"2024-05-13T15:40:06","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4700"},"modified":"2026-02-17T11:03:48","modified_gmt":"2026-02-17T11:03:48","slug":"bubble-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/bubble-sort\/","title":{"rendered":"Bubble sort – Blasen-Sortierung in Java"},"content":{"rendered":"

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 von Daten ist sehr wichtig f\u00fcr die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten ben\u00f6tigen.<\/p>\n

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.<\/p>\n

Um Ihnen die Auswahl zu erleichtern, stellen wir Ihnen in unserer Serie die bekanntesten Datensortieralgorithmen vor, erkl\u00e4ren ihre Prinzipien, Vor- und Nachteile und programmieren sie in Java.<\/p>\n

Heute werden wir uns mit Bubble<\/strong> Sort besch\u00e4ftigen.<\/p>\n

Algorithmus f\u00fcr Bubble sort<\/h2>\n

Bubble Sort ist ein Sortieralgorithmus, der nacheinander jeweils zwei benachbarte Elemente vergleicht und sie verwirft, bis sie in der gew\u00fcnschten Reihenfolge sortiert sind. Der Algorithmus erfordert mehrere Iterationen.<\/p>\n

Der Name des Algorithmus ist von den Luftblasen abgeleitet, die im Wasser an die Oberfl\u00e4che steigen. Analog dazu steigen bei dem Algorithmus die Elemente des Arrays in jeder Iteration bis zum Ende des unsortierten Teils des Arrays auf.<\/p>\n

Bubble Sort Algorithmus – Funktionsprinzip<\/h2>\n

Angenommen, wir m\u00f6chten die Elemente in aufsteigender Reihenfolge sortieren. Wenn ein Array nur ein Element hat, gilt es als sortiert, andernfalls m\u00fcssen die Elemente sortiert werden.<\/p>\n

Erste Iteration:<\/h3>\n

Alle zwei benachbarten Array-Elemente werden der Reihe nach vom Anfang des Arrays an verglichen. Wenn das erste Element gr\u00f6\u00dfer ist als das zweite, tauschen sie die Reihenfolge. Dann wird das zweite Element mit dem dritten verglichen, das dritte mit dem vierten, und so weiter. Die erste Iteration endet mit dem Vergleich der letzten benachbarten Elemente.<\/p>\n

W\u00e4hrend der ersten Iteration wird durch das Vertauschen der Elemente garantiert, dass das gr\u00f6\u00dfte Element des Arrays an das Ende des Arrays gelangt.<\/p>\n

Andere Iterationen:<\/h3>\n

Der letzte Index des Arrays wird als sortiert betrachtet, der Rest des Arrays ist noch nicht sortiert. F\u00fcr den unsortierten Teil des Arrays wird das Verfahren aus der ersten Iteration wiederholt. Bei jeder Iteration wird das gr\u00f6\u00dfte Element an das Ende des unsortierten Arrays vorgeblasen. Dies wird so lange wiederholt, bis das Array sortiert ist.<\/p>\n

Anzahl der Iterationen: n-1<\/strong>
\nAnzahl der Vergleiche: n*(n-1)\/2<\/strong><\/p>\n

Beispiel<\/h3>\n

Wir haben das folgende Array mit den Elementen [3][1][2]. Aus den Formeln berechnen wir, dass die Anzahl der ben\u00f6tigten Iterationen 2 und die Anzahl der Vergleiche 6 betr\u00e4gt.<\/p>\n

In der ersten Iteration finden die folgenden Operationen statt: [1][3][2] -> [1][2][3]. Das gr\u00f6\u00dfte Element 3 wird auf den letzten Index des Arrays abgebildet. Obwohl das Array bereits sortiert ist, wird eine zweite Iteration durchgef\u00fchrt, bei der die ersten beiden Elemente des Arrays verglichen werden. Da das erste und das zweite Element die richtige Reihenfolge haben, wird ihre Reihenfolge nicht vertauscht.<\/p>\n

Optimierung des Bubble Sort Algorithmus<\/h2>\n

Im obigen Beispiel haben wir gesehen, dass, wenn wir das Array bereits sortiert haben, dennoch unn\u00f6tigerweise zus\u00e4tzliche Iterationen und Vergleiche durchgef\u00fchrt werden. Das erh\u00f6ht nat\u00fcrlich die Laufzeit des Algorithmus. Die L\u00f6sung besteht darin, dass wir bei jeder Iteration feststellen, ob es eine Neuordnung zweier Elemente gibt. Wenn nicht, betrachten wir das Array als sortiert und f\u00fchren keine weiteren Iterationen durch. Diese Optimierung reduziert die Zeitkomplexit\u00e4t f\u00fcr ein bereits sortiertes Array und gew\u00e4hrleistet die Anpassungsf\u00e4higkeit des Algorithmus.<\/p>\n

Vorteile des Bubble-Sortieralgorithmus<\/h2>\n