Bubble Sort

Bubble Sort sortiert eine Liste, indem er immer wieder zwei benachbarte Werte vergleicht und vertauscht, wenn sie in der falschen Reihenfolge stehen. Das wiederholt er so lange, bis kein Tausch mehr nötig war.

In der Praxis wird er kaum eingesetzt, dafür ist er zu langsam. Als Einstieg ist er aber ideal: Man sieht mit bloßem Auge, was passiert, und begreift daran, warum ein Algorithmus bei doppelt so vielen Daten viermal so lange braucht.

Ein Durchlauf geht einmal von links nach rechts durch das Array:

1. Vergleiche das Element mit seinem rechten Nachbarn.
2. Steht der größere Wert links, tausche die beiden.
3. Gehe eine Position weiter.

Nach dem ersten Durchlauf steht der größte Wert ganz rechts, er ist wie eine Blase nach oben gestiegen. Deshalb muss der nächste Durchlauf ein Feld weniger prüfen, der übernächste zwei weniger und so weiter.

Wurde in einem kompletten Durchlauf kein einziges Mal getauscht, ist die Liste bereits sortiert und der Algorithmus hört sofort auf. Bei einer schon sortierten Liste genügt so ein einziger Durchlauf, und genau das ist der beste Fall mit O(n).

public static class BubbleSort
{
    // Sortiert das Array an Ort und Stelle, indem falsch stehende Nachbarn getauscht werden.
    public static void Sort(int[] numbers)
    {
        // Jeder Durchlauf schiebt den größten verbliebenen Wert ans Ende, deshalb wächst der
        // sortierte Bereich rechts pro Durchlauf um ein Element.
        for (var pass = 0; pass < numbers.Length - 1; pass++)
        {
            var swapped = false;

            for (var i = 0; i < numbers.Length - 1 - pass; i++)
            {
                if (numbers[i] <= numbers[i + 1])
                    continue;

                (numbers[i], numbers[i + 1]) = (numbers[i + 1], numbers[i]);
                swapped = true;
            }

            // In diesem Durchlauf wurde nichts getauscht, das Array ist also bereits sortiert.
            if (!swapped)
                return;
        }
    }
}

var numbers = new[] { 5, 1, 4, 2, 8 };

BubbleSort.Sort(numbers);

Console.WriteLine(string.Join(", ", numbers));

1, 2, 4, 5, 8

• Bubble Sort ist stabil: Gleiche Werte behalten ihre ursprüngliche Reihenfolge, weil nur bei einem echten größer getauscht wird.
• Er arbeitet in place, braucht also außer ein paar Variablen keinen zusätzlichen Speicher.
• Im Alltag nimmt man Array.Sort. Das ist ein hochoptimierter Mischalgorithmus, der je nach Datenmenge das Verfahren wechselt.

Zum Spielen: Lass die Abbruchbedingung mit swapped weg. Das Ergebnis bleibt richtig, aber der beste Fall verschwindet.