Bubble Sort

Bubble Sort ist ein einfacher, iterativer Sortieralgorithmus, der durch wiederholtes Vergleichen benachbarter Elemente funktioniert.

Er vertauscht die Elemente, wenn sie in der falschen Reihenfolge stehen. Große Elemente "blubbern" wie Blasen nach oben (Ende des Arrays). Dieser Vorgang wird wiederholt, bis das Array vollständig sortiert ist.

Zeitkomplexität

• Best-Case: 4. Big O(n) - Das Array ist bereits sortiert, nur ein Durchlauf nötig
• Worst-Case: 6. Big O(n²) - Array ist umgekehrt sortiert, n Durchläufe mit n Vergleichen

Implementierungen

Java

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // Optimierung: bereits sortiert
        }
    }
}

Python

def bubblesort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

C Sprache

#include <stdio.h>

void bubblesort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}