Bubble Sort

5.1 Definition von Bubble Sort

Bubble Sort ist ein einfacher Sortieralgorithmus, der wiederholt durch die Liste läuft, benachbarte Elemente vergleicht und diese tauscht, wenn sie in der falschen Reihenfolge sind. Dieser Prozess wird fortgesetzt, bis die Liste vollständig sortiert ist.

Funktionsweise:

1. Der Algorithmus läuft durch die Liste und vergleicht jedes Paar benachbarter Elemente.
2. Wenn die Elemente in der falschen Reihenfolge sind (das erste ist größer als das zweite für eine aufsteigende Sortierung), werden sie getauscht.
3. Dieser Prozess wird für alle Paare von Elementen in der Liste wiederholt.
4. Nach jedem vollständigen Durchgang "schwimmt" das größte Element an seinen Platz (wie eine Blase auf der Wasseroberfläche) und wird daher bei den nächsten Durchgängen nicht mehr berücksichtigt.
5. Der Prozess wird fortgesetzt, bis die Liste sortiert ist.

Zeit- und Speicherkomplexität von Bubble Sort

Zeitkomplexität:

• Im schlimmsten Fall: O(n^2) — tritt auf, wenn die Elemente anfangs in umgekehrter Reihenfolge angeordnet sind.
• Im durchschnittlichen Fall: O(n^2) — tritt bei zufälliger Anordnung der Elemente auf.
• Im besten Fall: O(n) — tritt auf, wenn die Elemente bereits sortiert sind (der Algorithmus kann für diesen Fall optimiert werden, indem überprüft wird, ob ein Tausch bei einem Durchgang stattgefunden hat).

Speicherkomplexität:

O(1) — da der Algorithmus eine konstante Menge an zusätzlichem Speicher verwendet (nur einige Variablen zum Speichern temporärer Werte).

5.2 Implementierung des Algorithmus

Der Bubble Sort-Algorithmus ist der einfachste und grundlegendste Algorithmus zum Sortieren von Listen/Arrays von Elementen. Er vergleicht einfach Paare von Elementen und tauscht sie aus, wenn nötig.

Version 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Austausch von Elementen

print("Sortiertes Array:", array)
# Ausgabe: Sortiertes Array: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Die innere Schleife (grün hervorgehoben) vergleicht ein Element mit seinem rechten Nachbarn. Und wenn nötig, werden die Elemente getauscht.

Version 2:

Wir können unserem Algorithmus sofort eine Optimierung hinzufügen: Nach dem ersten Durchlauf wird das größte Element ganz rechts sein, daher muss es beim nächsten Zyklus nicht mehr berücksichtigt werden.

Nach der zweiten Iteration befinden sich bereits 2 maximale Elemente rechts, daher kann die innere Schleife bis n - 1 - i gehen, wobei i die Anzahl der durchgeführten Iterationen der äußeren Schleife ist.

Die neue Version sieht so aus:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Austausch von Elementen

print("Sortiertes Array:", array)
# Ausgabe: Sortiertes Array: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Version 3:

Auch das Array könnte bereits fast sortiert sein. Daher kann man eine solche Optimierung hinzufügen: Wenn die innere Schleife alle Elemente durchlaufen hat, aber keinen einzigen Tausch gemacht hat, ist die Sortierung abgeschlossen.

In dieser Version wird die Variable swapped verwendet, um zu verfolgen, ob ein Tausch während des letzten Durchgangs stattgefunden hat. Wenn nach dem Durchlauf durch das Array kein Tausch stattgefunden hat, bedeutet dies, dass das Array bereits sortiert ist und das Ausführen weiterer Iterationen sinnlos ist — sie werden die Sortierung nicht verbessern. So ermöglicht die Variable swapped, den Algorithmus bei fast sortierten Arrays erheblich zu beschleunigen und seine Ausführung vorzeitig zu beenden.

Umsetzung des Bubble Sort in Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False  # Optimierung: Prüfung, ob ein Tausch stattgefunden hat
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # Austausch von Elementen
                swapped = True
        if not swapped:
            break  # Wenn keine Tausche stattfanden, ist das Array bereits sortiert
    return array

# Beispiel der Benutzung:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Sortiertes Array:", sorted_array)
# Ausgabe: Sortiertes Array: [11, 12, 22, 25, 34, 64, 90]