Vergleiche beim qsort berechnen in C

Question

Meine Aufgabe ist es den qsort selbst zu schreiben und die Vergleiche ausgeben (das Ganze in C). Mein Code sieht folgendermaßen aus:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void init(int a[], size_t n);
int quick_sort(int a[], int n);

int main(void) {
    int arr[1000];
    int i, anz = 0;

    srand((unsigned) time(NULL));
    init(arr, 1000);
    printf("Ungeordnet:\n\n");

    for (i = 0; i < 1000; i++) {
        printf("%5d\n", arr[i]);
    }

    anz = quick_sort(arr, 1000);

    for (i = 0; i < 1000; i++) {
        printf("%5d\n", arr[i]);
    }

    printf("%d", anz);

    return 0;
}

void init(int a[], size_t n) {
    int i, x = 0;
    for (i = 0; i < (signed) n; i++) {
        x = rand() % 10000;
        a[i] = x;
    }
}

int quick_sort(int a[], int n) {
    int l = 0, r = n - 1, p = a[0];
    int anz = 0;

    if (n <= 1) {
        return 0;
    } else {

    }
    while (l < r) {
        while (a[r] > p && l < r) {
            r--;
        }
        if (l < r) {
            a[l] = a[r];
            l++;
        }
        anz++;
        while (a[l] < p && l < r) {
            l++;
        }
        if (l < r) {
            a[r] = a[l];
            r--;
        }
        anz++;
    }

    a[l] = p;
    quick_sort(a, l);
    quick_sort(a + l + 1, n - l - 1);

    return anz;
}

Die Ausgabe der Vergleiche beträgt hier rund 70. Ich glaube nicht, dass das stimmt, kann mir da wer helfen? Sortiert ausgegeben wird es aber.

Answer 1

while (a[r] > p && l < r) {
    r--;
}

Bei jedem Schleifendurchlauf vergleichst du, erhöhst anz aber nicht.

anz++;

Diese Erhöhung basiert nicht auf einem Vergleich.

while (a[l] < p && l < r) {
    l++;
} 

Bei jedem Schleifendurchlauf vergleichst du, erhöhst anz aber nicht.

anz++;

In Anbetracht des vorhergehenden a++ hättest du auch gleich a += 2 schreiben können.

    quick_sort(a, l);
    quick_sort(a + l + 1, n - l - 1);

Die Vergleiche in den rekursiven Aufrufen werden ebenfalls nicht mitgezählt. Stattdessen:

    anz += quick_sort(a, l);
    anz += quick_sort(a + l + 1, n - l - 1);