C/C++-Algorithmen

Quick Sort

Quick Sort platziert ein Pivot endgültig und sortiert beide Partitionen rekursiv.

Was ist Quick Sort?

Quick Sort platziert ein Pivot endgültig und sortiert beide Partitionen rekursiv.

Partitioniere Werte um ein Pivot.

Wichtige Punkte

Teste leere, einzelne, doppelte und sortierte Eingaben.
Trenne Korrektheit von Optimierung.
Nutze in Produktivcode bevorzugt die Standardbibliothek.

Quick Sort visualisieren

O(n log n)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Codebeispiele in C und C++

Code ausführen →

main.c

#include <stdio.h>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}

Erwartete Ausgabe

3 4 5 7 9 10

C++

Code ausführen →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}

Erwartete Ausgabe

3 4 5 7 9 10

Vergleich zwischen C und C++

Im Mittel O(n log n), bei ungünstigen Pivots O(n²). C++ drückt die Partitionierung mit std::partition aus.

Schleifen, Pointer, Längen und Puffer sind explizit.

C++

Iteratoren und Algorithmen trennen Operation und Speicherung.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Verfolge jeden Vergleich manuell.
Teste Duplikate und Extremwerte.
Vergleiche die Laufzeit mit der Standardbibliothek.