BubbleSort und SelectionSort

Das Sortieren einer Folge gehört zu den wichtigsten Aufgaben der Informatik, weil viele weitere Algorithmen (etwa die binäre Suche) sortierte Daten voraussetzen. Im Abitur werden zunächst die einfachen, quadratischen Verfahren BubbleSort und SelectionSort behandelt. Beide eignen sich besonders, um das Prinzip von Vergleichen und Vertauschen sowie die Analyse mit Schleifeninvarianten zu üben.

BubbleSort vergleicht in jedem Durchlauf benachbarte Elemente und vertauscht sie, falls sie in falscher Reihenfolge stehen. Große Werte „steigen“ dadurch wie Blasen ans Ende. Nach \( n-1 \) Durchläufen ist das Array sortiert.

Java-Implementierung:

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

Python-Implementierung:

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

SelectionSort sucht in jedem Durchlauf das kleinste verbleibende Element und vertauscht es mit dem ersten unsortierten Element. So entsteht von links her ein bereits sortierter Bereich.

Java-Implementierung:

public static void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) min = j;
        }
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

Python-Implementierung:

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

Beide Verfahren benötigen zwei verschachtelte Schleifen. Die Zahl der Vergleiche ist in der Summe \( \frac{n(n-1)}{2} \), also \( \mathcal{O}(n^2) \). BubbleSort kann mit einer frühen Abbruchprüfung (kein Tausch im Durchlauf) im besten Fall auf \( \mathcal{O}(n) \) verbessert werden, wenn das Array schon sortiert ist. SelectionSort hingegen ist immer \( \mathcal{O}(n^2) \), tauscht aber nur \( n-1 \)-mal.

BubbleSort ist stabil (gleichwertige Elemente behalten ihre Reihenfolge), SelectionSort dagegen nicht. Für praktische Aufgaben sind beide Verfahren wegen der quadratischen Laufzeit zu langsam und werden nur auf sehr kleinen Datenmengen oder im Unterricht eingesetzt. Für echte Anwendungen verwendet man Algorithmen mit \( \mathcal{O}(n \log n) \) wie MergeSort oder QuickSort.

Beim Tausch wird oft die Hilfsvariable vergessen oder falsch eingesetzt. Bei BubbleSort wird die innere Schleifengrenze gerne falsch gesetzt (n statt n - 1 - i), wodurch ein ArrayIndexOutOfBounds-Fehler entsteht. Bei SelectionSort wird oft der falsche Index als Minimum gemerkt.

Zusammenfassung: BubbleSort und SelectionSort sind einfach zu verstehen, aber mit \( \mathcal{O}(n^2) \) langsam. Sie eignen sich vor allem als Lehrbeispiele für den Aufbau und die Analyse von Algorithmen.

Abitur-Tipp: Zähle die Vergleiche und Vertauschungen für ein konkretes Beispiel mit fünf Zahlen Schritt für Schritt durch – das ist eine typische Prüfungsaufgabe.