Vorlesung Informatik 2 - Teil B: Theorie
2.2 Bubble Sort
Dieser Sortieralgorithmus ist ebenfalls recht einfach
In einem inneren Schritt gehen wir von links nach rechts durch das Array und vergleichen jedes Element mit seinem rechten Nachbarn. Falls dieser kleiner ist als das aktuelle Element, vertauschen wir das Paar, so dass sie zueinander in der richtigen Reihenfolge stehen.
Wenn ein solcher Schritt fertig ist, steht das größte Element an seinem richtigen Platz - es ist wie eine Blase im Sektglas aufgestiegen. Der sortierte Bereich wächst also von rechts nach links jeweils um ein Element.
Wir wiederholen diesen Schritt, wobei wir den Bereich des Arrays, der noch sortiert werden muss, um 1 reduzieren.
Bubble Sort ist stabil, in-situ und hat die Komplexität O(N2)