Deutsche Lernausgabe

Quicksort in C

Verstehen Sie Pivot, Partitionierung und ungünstige Fälle von Quicksort.

Quicksort wählt ein Pivot, trennt kleinere von größeren Werten und sortiert beide Teile rekursiv. Bei der Lomuto-Partitionierung dieses Beispiels ist das letzte Element das Pivot; ein Index markiert den bereits bearbeiteten Bereich.

Die Rekursion endet bei Intervallen mit weniger als zwei Elementen. Die mittlere Laufzeit beträgt O(N log N), stark unausgewogene Partitionen können jedoch O(N²) verursachen. Berücksichtigen Sie auch ohne zweites Array den Aufrufstack.

Testen Sie Duplikate, bereits sortierte Arrays und umgekehrte Reihenfolgen. Prüfen Sie die Grenzen jedes Aufrufs. Diese Variante garantiert keine Erhaltung der ursprünglichen Reihenfolge gleicher Elemente.

Quellcode

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Im Compiler öffnen

Erwartetes Ergebnis

Sorted array:
10 30 40 50 70 80 90

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.