Bubble Sort

Bubble Sort ist ein einfacher Sortieralgorithmus, der wiederholt benachbarte Elemente vergleicht und vertauscht, bis das Array sortiert ist. Er ist besonders für Lehrzwecke geeignet, aber aufgrund seiner 'O(n^2)'-Komplexität ungeeignet für große Datenmengen.

Funktionsweise

Der Algorithmus durchläuft das Array mehrfach. Bei jedem Durchlauf „blubbert“ das größte unsortierte Element an seine korrekte Position. Durch frühzeitiges Abbrechen, falls kein Tausch erfolgte, kann die Effizienz im besten Fall auf 'O(n)' verbessert werden.

Quelle¹

Java-Implementierung (optimiert)

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Tausche Elemente
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // Frühzeitiger Abbruch
        }
    }

    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(data);
        System.out.print("Sortiert: ");
        for (int i : data) System.out.print(i + " ");
    }
}

Eigenschaften

| Merkmal | Wert | |——–|——| | Best-Case | 'O(n)' | | Worst-Case | 'O(n^2)' | | Speicher | 'O(1)' | | Stabil | Ja |