Bubble-Sort

Einführung

Selbst kleinste Fehler in der Datenreihenfolge können enorme Auswirkungen haben

Eine unsortierte Kontaktliste erschwert die Suche, ein falsch einsortierter Datensatz kann ganze Auswertungen verfälschen. Effizientes Sortieren ist deshalb eine Kernaufgabe in der Informatik.

Vorher-Nachher: Vom Chaos zur Ordnung durch paarweises Vergleichen und Tauschen — Bildrechte: Ausbildung-in-der-IT.de (KI-unterstützt)

Um dieses Prinzip zu verstehen, beginnen wir mit einem besonders einfachen Algorithmus: Bubble Sort.

An ihm lernst du die grundlegenden Ideen des Sortierens kennen, bevor wir später auf leistungsfähigere Verfahren eingehen.

Lernziele

Nach dieser Lerneinheit kannst du:

• Sortieren erklären: Du beschreibst, was Sortieren bedeutet, nennst typische Anwendungsfälle und erläuterst, warum es für effiziente Datenverarbeitung unverzichtbar ist.
• Bubble Sort verstehen: Du erklärst den Ablauf des Algorithmus Schritt für Schritt, inklusive Vergleichen, Tauschoperationen, Durchgängen und der Abbruchbedingung bei „kein Tausch“.
• Komplexität und Vergleich beurteilen: Du analysierst die Zeit- und Speicherkomplexität von Bubble Sort, bewertest die Effizienz in Best-, Average- und Worst-Case-Szenarien und vergleichst ihn mit Quick Sort und Merge Sort.

Bedeutung: Sortieren

Sortieren bedeutet, Daten in eine bestimmte Reihenfolge zu bringen. Du kennst das aus dem Alltag: Wenn du einen Stapel Karteikarten mit Zahlen hast und sie der Größe nach ordnest, sortierst du. Genau das macht ein Sortieralgorithmus mit Daten im Computer.

Sortieren ist wichtig, weil:

• sortierte Daten schneller durchsucht werden können.
• viele Algorithmen nur mit sortierten Daten korrekt arbeiten.
• es in der Praxis häufig vorkommt (z. B. Kontaktlisten, Suchergebnisse, Produktkataloge).

Was ist Bubble Sort?

Bubble Sort ist ein sehr einfacher Sortieralgorithmus. Er funktioniert nach dem Prinzip, dass benachbarte Elemente miteinander verglichen und gegebenenfalls vertauscht werden, bis alle Elemente in der richtigen Reihenfolge stehen.

Bubble-Sort — (Bildrechte: Ausbildung in der IT)

Die Idee:

• Vergleiche immer zwei benachbarte Elemente.
• Wenn sie in der falschen Reihenfolge stehen, tausche sie.
• Nach jedem Durchgang ist das größte Element am Ende angekommen.

Warum heißt er “Bubble Sort”?

Der Name kommt daher, dass die größten Elemente wie Luftblasen nach oben “aufsteigen”. Die kleineren Werte “sinken” nach unten. So steht nach jedem Durchlauf das größte Element an der richtigen Position.

Bubble Sort Beispiel (Bildrechte: Ausbildung in der IT)

Schritt-für-Schritt Beispiel

Nehmen wir das Array: [5, 2, 8, 1, 9]

Durchgang 1:

1. Vergleiche 5 und 2 → 5 > 2 → tauschen → [2, 5, 8, 1, 9]
2. Vergleiche 5 und 8 → 5 < 8 → kein Tausch
3. Vergleiche 8 und 1 → 8 > 1 → tauschen → [2, 5, 1, 8, 9]
4. Vergleiche 8 und 9 → 8 < 9 → kein Tausch

Ergebnis: Die größte Zahl (9) ist am Ende. [2, 5, 1, 8, 9]

Durchgang 2:

1. Vergleiche 2 und 5 → 2 < 5 → kein Tausch
2. Vergleiche 5 und 1 → 5 > 1 → tauschen → [2, 1, 5, 8, 9]
3. Vergleiche 5 und 8 → 5 < 8 → kein Tausch

Ergebnis: Die zweitgrößte Zahl (8) ist am Ende. [2, 1, 5, 8, 9]

Durchgang 3:

1. Vergleiche 2 und 1 → 2 > 1 → tauschen → [1, 2, 5, 8, 9]

Fertig: Das Array ist sortiert. [1, 2, 5, 8, 9]

Wichtige Erkenntnisse

• Für n Elemente braucht Bubble Sort maximal n-1 Durchgänge.
• In jedem Durchgang kommt ein Element an die richtige Position.
• Optimierung: Wenn in einem Durchgang nichts getauscht wird, ist das Array bereits sortiert.

Vorteile und Nachteile

Bevor du Bubble Sort einsetzt, solltest du seine Stärken und Schwächen kennen. Die folgende Tabelle zeigt die wichtigsten Vorteile und Nachteile im Überblick.

Vorteile	Nachteile
Sehr einfach zu verstehen und zu implementieren	Sehr langsam bei großen Datenmengen (O(n²))
Stabil: Gleiche Elemente behalten ihre relative Reihenfolge	Viele unnötige Vergleiche auch bei fast sortierten Arrays
In-Place: Braucht keinen zusätzlichen Speicher
Optimal für bereits sortierte Arrays (Best Case: O(n))

Die Tabelle verdeutlicht, dass Bubble Sort zwar leicht zu lernen und umzusetzen ist, sich jedoch nicht für große Datenmengen eignet.

Praktische Einsatzgebiete

Bubble Sort wird in der Praxis selten für produktive Systeme genutzt. Er eignet sich aber in bestimmten Szenarien gut.

1. Lernzwecke: Perfekt zum Verstehen von Sortieralgorithmen
2. Sehr kleine Datensätze: Bis ca. 10–20 Elemente
3. Fast sortierte Daten: Wenn nur wenige Elemente falsch stehen
4. Einfache Implementierung: Wenn Code-Einfachheit wichtiger ist als Effizienz

⏳ Lädt Dataview-Inhalt...

Java-Implementierung von Bubble Sort

Nachdem du die Funktionsweise von Bubble Sort kennengelernt hast, siehst du hier eine vollständige Java-Implementierung. Der Code enthält Kommentare, die die einzelnen Schritte erklären.

public class BubbleSort {
    // Hauptmethode für Bubble Sort Algorithmus
    public static void bubbleSort(int[] array) {
        int n = array.length;
        // Äußere Schleife: n-1 Durchgänge
        for (int i = 0; i < n - 1; i++) {
            boolean getauscht = false; // Optimierung: Flag für Tausch
            for (int j = 0; j < n - i - 1; j++) {
                // Wenn linkes Element größer ist als rechtes
                if (array[j] > array[j + 1]) {
                    // Tausche die beiden Elemente
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    getauscht = true; // Merke, dass getauscht wurde
                }
            }
            // Optimierung: Wenn nichts getauscht wurde, ist Array sortiert
            if (!getauscht) {
                break;
            }
        }
    }
 
    // Hilfsmethode zum Ausgeben des Arrays
    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
 
    // Hauptprogramm
    public static void main(String[] args) {
        int[] zahlen = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Unsortiertes Array:");
        printArray(zahlen);
        bubbleSort(zahlen);
        System.out.println("Sortiertes Array:");
        printArray(zahlen);
    }
}

Dieser Code implementiert Bubble Sort in Java. Zuerst wird das Array unsortiert ausgegeben, dann sortiert und anschließend erneut ausgegeben.

Erklärung der Codebestandteile

• Äußere Schleife (for (int i = 0; i < n - 1; i++)): Bestimmt die Anzahl der Durchgänge. Für ein Array mit n Elementen benötigen wir maximal n-1 Durchgänge.
• Innere Schleife (for (int j = 0; j < n - i - 1; j++)): Vergleicht benachbarte Elemente. Mit jedem Durchgang muss ein Element weniger betrachtet werden, da es bereits an der richtigen Position ist.
• Optimierung (boolean getauscht): Wenn in einem Durchgang keine Vertauschung stattfindet, ist das Array bereits sortiert. Das spart unnötige Vergleiche.

Effizienz und Komplexität

Bubble Sort ist einfach, aber nicht effizient für große Datenmengen. Die Komplexität ist wie folgt:

• Zeitkomplexität:

  • Best Case: O(n) – wenn das Array bereits sortiert ist
  • Average Case: O(n²) – im Durchschnitt
  • Worst Case: O(n²) – wenn das Array umgekehrt sortiert ist

• Speicherplatzkomplexität: O(1) – konstanter Speicherbedarf, da nur Hilfsvariablen benötigt werden

• Eigenschaft: In-Place Algorithmus, sortiert das Array direkt ohne zusätzlichen Speicher

Vergleich mit anderen Sortieralgorithmen

Die folgende Tabelle zeigt Bubble Sort im Vergleich zu Quick Sort und Merge Sort:

Algorithmus	Best Case	Worst Case	Speicher	Stabil
Bubble Sort	O(n)	O(n²)	O(1)	Ja
Quick Sort	O(n log n)	O(n²)	O(log n)	Nein
Merge Sort	O(n log n)	O(n log n)	O(n)	Ja

Dieser Vergleich macht deutlich, dass Bubble Sort zwar einfach zu verstehen und zu implementieren ist, aber in Bezug auf Effizienz deutlich schlechter abschneidet als Quick Sort oder Merge Sort.

⏳ Lädt Dataview-Inhalt...

Zusammenfassung

Zusammenfassung:

Grundlagen des Sortierens und Bubble Sort

Sortieren bedeutet, Daten in eine bestimmte Reihenfolge zu bringen. Dies ist zentral, da viele Algorithmen sortierte Daten benötigen und Anwendungen wie Kontaktlisten oder Produktkataloge davon abhängen.

• Sortieren strukturiert Daten und macht sie effizient nutzbar.
• Bubble Sort vergleicht benachbarte Elemente und tauscht sie bei Bedarf.
• Nach jedem Durchgang steht ein Element an der richtigen Position.
• Maximale Durchgänge: n-1 für ein Array mit n Elementen.
• Optimierung: Wenn kein Tausch erfolgt, ist das Array bereits sortiert.

Vorteile und Nachteile von Bubble Sort

Bubble Sort ist leicht verständlich, aber ineffizient für große Datenmengen. Eine tabellarische Übersicht:

Vorteile	Nachteile
Sehr einfach zu verstehen und zu implementieren	Sehr langsam bei großen Datenmengen (O(n²))
Stabil: Gleiche Elemente behalten ihre Reihenfolge	Viele unnötige Vergleiche auch bei fast sortierten Arrays
In-Place: Kein zusätzlicher Speicherbedarf
Optimal für bereits sortierte Arrays (Best Case: O(n))

Praktische Einsatzgebiete

Bubble Sort eignet sich vor allem in Lernsituationen und für kleine Datensätze.

• Lernzwecke: Ideal zum Verstehen von Sortieralgorithmen.
• Sehr kleine Datensätze: Bis ca. 10–20 Elemente.
• Fast sortierte Daten: Wenn nur wenige Elemente falsch stehen.
• Einfache Implementierung: Wenn Code-Einfachheit wichtiger ist als Effizienz.

Java-Implementierung von Bubble Sort

Bubble Sort lässt sich einfach in Java implementieren. Der Algorithmus nutzt zwei Schleifen:

• Äußere Schleife: Steuert die Anzahl der Durchgänge.
• Innere Schleife: Vergleicht und tauscht benachbarte Elemente.
• Optimierung: Ein Flag beendet den Algorithmus frühzeitig, wenn keine Vertauschungen mehr nötig sind.

Effizienz und Vergleich mit anderen Algorithmen

• Zeitkomplexität: O(n) im Best Case, O(n²) im Durchschnitt und Worst Case.
• Speicherplatz: O(1), da keine zusätzlichen Datenstrukturen benötigt werden.
• Stabiler Algorithmus: Gleiche Elemente behalten ihre Reihenfolge.

Vergleich zu anderen Sortierverfahren:

• Quick Sort: Sehr effizient (O(n log n) Best Case), aber nicht stabil.
• Merge Sort: Effizient (O(n log n) in allen Fällen) und stabil, benötigt jedoch zusätzlichen Speicher.
• Bubble Sort: Leicht verständlich, aber ineffizient für große Datenmengen.

Ausblick:

In der nächsten Lerneinheit geht es um den Selection-Sort-Algorithmus, ein grundlegendes Verfahren zur Sortierung von Datenlisten. Du lernst, wie bei diesem Algorithmus in jedem Durchlauf das kleinste (oder größte) Element ausgewählt und an die richtige Position verschoben wird. Außerdem erfährst du, wie sich Selection-Sort in Bezug auf Laufzeit und Speicherbedarf von anderen Sortierverfahren unterscheidet.

---