Bubblesort

Von Julian Sauer

18. März 2023 - 3 Minuten - 617 Wörter

Einleitung

Sortieralgorithmen sind ein essenzieller Teil in der Informatik und werden in vielen Anwendungen wie Suchen, Datenanalyse und Kryptographie verwendet. Einer der einfachsten Sortieralgorithmen ist Bubblesort. In diesem Artikel werden wir uns anschauen, wie er funktioniert und was seine Laufzeitkomplexität ist.

Inhaltsverzeichnis

Funktionsweise

Bubblesort tauscht wiederholt benachbarte Elemente, wenn sie in der falschen Reihenfolge sind. Dadurch wandern nach und nach die größten Elemente an das Ende des Arrays - ähnlich wie Blasen, die in Wasser aufsteigen.

Beginn am Anfang des Arrays.
Vergleiche die ersten beiden Elemente: Ist das Erste größer als das Zweite, vertausche sie.
Gehe zum nächsten Paar und wiederhole Schritt 2. bis das Ende des Arrays erreicht ist.
Falls Elemente vertauscht wurden, wiederhole Schritt 1. Andernfalls ist das Array sortiert.

Hier ist ein Beispiel mit Zahlen. Die markierten Paare werden jeweils links verglichen und rechts ggf. vertauscht.

1. Iteration: 4 2 8 1 5 -> 2 4 8 1 5
              ^ ^          ^ ^
              
              2 4 8 1 5 -> 2 4 8 1 5
                ^ ^          ^ ^
              
              2 4 8 1 5 -> 2 4 1 8 5
                  ^ ^          ^ ^
              
              2 4 1 8 5 -> 2 4 1 5 8
                    ^ ^          ^ ^

2. Iteration: 2 4 1 5 8 -> 2 4 1 5 8
              ^ ^          ^ ^
              
              2 4 1 5 8 -> 2 1 4 5 8
                ^ ^          ^ ^
              
              2 1 4 5 8 -> 2 1 4 5 8
                  ^ ^          ^ ^
              
              2 1 4 5 8 -> 2 1 4 5 8
                    ^ ^          ^ ^

3. Iteration: 2 1 4 5 8 -> 1 2 4 5 8
              ^ ^          ^ ^
              
              1 2 4 5 8 -> 1 2 4 5 8
                ^ ^          ^ ^
              
              1 2 4 5 8 -> 1 2 4 5 8
                  ^ ^          ^ ^
              
              1 2 4 5 8 -> 1 2 4 5 8
                    ^ ^          ^ ^

4. Iteration: kein weiterer Tausch nötig

Laufzeitkomplexität

So einfach der Algorithmus ist, so ineffizient ist er leider auch: Es wird in jeder Iteration jedes Paar verglichen. Bei n Elementen sind es also n - 1 Vergleiche pro Iteration. Und da wir pro Iteration immer nur garantieren können, dass das nächstgrößte Element an die richtige Position geschoben wird, brauchen wir im Worst Case auch n Iterationen, bis alle Elemente an der richtigen Stelle angekommen sind. Das bringt uns zu einer Komplexität von O(n²) im Worst Case. Im Best Case sind unsere Elemente bereits sortiert, sodass wir das in einer Laufzeit von O(n) lediglich verifizieren.

Implementierungen

Java

public static void bubbleSort(int[] input) {
    int n = input.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (input[j] > input[j+1]) {
                int temp = input[j];
                input[j] = input[j+1];
                input[j+1] = temp;
            }
        }
    }
}

Kotlin

fun bubbleSort(input: IntArray) {
    val n = input.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (input[j] > input[j + 1]) {
                val temp = input[j]
                input[j] = input[j + 1]
                input[j + 1] = temp
            }
        }
    }
}

Python

def bubbleSort(input):
    n = len(input)
    for i in range(n-1):
        for j in range(0, n-i-1):
            if input[j] > input[j+1] :
                input[j], input[j+1] = input[j+1], input[j]

Go

func bubbleSort(input []int) {
    n := len(input)
    for i := 0; i < n - 1; i++ {
        for j := 0; j < n - i - 1; j++ {
            if input[j] > input[j+1] {
                input[j], input[j+1] = input[j+1], input[j]
            }
        }
    }
}