Quick Sort

Quick Sort sortiert, ohne jemals zwei Hälften zusammenfügen zu müssen. Stattdessen wählt er einen Wert als Pivot und ordnet das Array so um, dass links davon nur kleinere und rechts davon nur größere Werte stehen.

Danach steht das Pivot bereits an seiner endgültigen Position, und dasselbe Verfahren wird auf die beiden Seiten angewendet. In der Praxis ist Quick Sort meist der schnellste der klassischen Sortieralgorithmen.

Der Kern ist das Partitionieren. Hier wird das letzte Element des Abschnitts als Pivot genommen:

1. Eine Grenze markiert die erste Position, die noch zum größeren Teil gehört. Sie startet ganz links.
2. Jedes Element wird mit dem Pivot verglichen. Ist es kleiner oder gleich, wird es an die Grenze getauscht und die Grenze rückt eine Stelle weiter.
3. Am Ende wird das Pivot selbst auf die Grenze getauscht.

Jetzt gilt: Alles links vom Pivot ist kleiner, alles rechts davon größer. Das Pivot muss nie wieder bewegt werden. Für die beiden Abschnitte links und rechts beginnt das Ganze von vorn, bis ein Abschnitt weniger als zwei Elemente hat.

public static class QuickSort
{
    // Sortiert das Array an Ort und Stelle.
    public static void Sort(int[] numbers) => Sort(numbers, 0, numbers.Length - 1);

    private static void Sort(int[] numbers, int left, int right)
    {
        // Ein Abschnitt mit weniger als zwei Elementen ist bereits sortiert.
        if (left >= right)
            return;

        var pivotIndex = Partition(numbers, left, right);

        // Das Pivot steht an seinem endgültigen Platz, es bleiben nur die beiden Seiten.
        Sort(numbers, left, pivotIndex - 1);
        Sort(numbers, pivotIndex + 1, right);
    }

    // Schiebt jeden Wert, der kleiner als das Pivot ist, nach links davon
    // und liefert die Position, an der das Pivot landet.
    private static int Partition(int[] numbers, int left, int right)
    {
        var pivot = numbers[right]; // das letzte Element des Abschnitts dient als Pivot
        var boundary = left;        // erste Stelle, die zum Teil "größer als das Pivot" gehört

        for (var i = left; i < right; i++)
        {
            if (numbers[i] > pivot)
                continue;

            (numbers[i], numbers[boundary]) = (numbers[boundary], numbers[i]);
            boundary++;
        }

        // Zum Schluss wird das Pivot selbst auf die Grenze getauscht.
        (numbers[right], numbers[boundary]) = (numbers[boundary], numbers[right]);

        return boundary;
    }
}

var numbers = new[] { 9, 4, 7, 1, 3, 8, 2 };

QuickSort.Sort(numbers);

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

1, 2, 3, 4, 7, 8, 9

• Die Laufzeit hängt vom Pivot ab. Teilt es das Array jedes Mal ungefähr in der Mitte, ergeben sich O(n log n) Schritte. Trifft es immer den größten Wert, entartet es zu O(n²).
• Genau das passiert bei bereits sortierten Daten, wenn man wie hier stur das letzte Element nimmt. Echte Implementierungen wählen das Pivot deshalb zufällig oder als Median aus drei Kandidaten.
• Quick Sort ist nicht stabil: Beim Tauschen über größere Distanzen kann sich die Reihenfolge gleicher Werte ändern.