Nederlandse leereditie

Quicksort in C: uitgelegd voorbeeld

Sorteer een array met partitionering en recursie en controleer grenzen en slechtste gevallen.

Quicksort kiest een pivot, scheidt kleinere en grotere waarden en sorteert de delen recursief. Bij de Lomuto-partitionering in dit voorbeeld is het laatste element de pivot en begrenst een index het verwerkte gebied.

Recursie stopt wanneer het interval minder dan twee elementen bevat. De gemiddelde tijd is O(N log N), maar sterk ongelijke partities kunnen O(N²) kosten. Tel ook de aanroepstack mee, zelfs zonder tweede array.

Test duplicaten, gesorteerde arrays en omgekeerde volgorde. Controleer de grenzen van elke aanroep. Deze versie garandeert niet dat gelijke elementen hun oorspronkelijke volgorde behouden.

Broncode

#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;
}

Openen in de compiler

Verwacht resultaat

Sorted array:
10 30 40 50 70 80 90

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.