QuickSort algorithm with Hoare partitioning in C

Question

I'm having an issue with this Quicksort algorithm:

void swap(int *x, int *y) {
    int tmp;

    tmp = *x;
    *x = *y;
    *y = tmp;
}

int partition (int *arr, int min, int max) {
    int x = arr[min];
    int i = min - 1;
    int j = max + 1;

    while (1) {
        do {
            j--;
        } while (i < j && arr[j] < x);
        do {
            i++;
        } while (arr[i] > x);
        if  (i < j)
            swap(&arr[i], &arr[j]);
        else
            return j + 1;
    }
}

void quickSort(int *arr, int inf, int sup) {
    if (arr) {
        if (inf < sup) {
            int pivot = partition(arr, inf, sup);
            //printf("pivot = %d", pivot);
            quickSort(arr, inf, pivot - 1);
            quickSort(arr, pivot + 1, sup);
        }
    }
}

int main() {
    int array[] = { 151, 153, 134, 137, -1, -1, -1, -1, -1, 158, 158, -1, -1, 133, 127, 158, 158 };

    int dim = sizeof(array) / sizeof(int);
    quickSort(array, 0, dim - 1);

    for (int i = 0; i < dim; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

It's supposed to return a descending sorted array but it doesn't for some reasons.

The input:(the rest of the 512 elements-long array is made of -1)

151 153 134 137 -1 -1 -1 -1 -1 158 158 -1 -1 133 127 158 158

The output:

158 158 158 153 158 -1 151 134 137 133 127 -1 -1 -1 -1 -1 -1

Expected output:

158 158 158 158 153 151 137 134 133 127 -1 -1 -1 -1 -1 -1 -1

I'm expecting the algorithm to return a descending sorted array. I've tried to switch the input but nothing seems to be working.

Answer 1

First of all, you need to carefully debug your partition function. The return value should be j

int partition (int *arr,int min, int max){
    int x=arr[min];
    int i=min-1;
    int j=max+1;

    while (1) {
        do {
            j--;
        } while (i < j && arr[j] < x);
        do {
            i++;
        } while (arr[i] > x);
        if  (i < j)
            swap(&arr[i],&arr[j]);
        else
            return j;
    }
}

You can use gdb or any ide to debug the main flow and you can get the logic. For quickSort func, you should use inf->pivot, pivot + 1 -> sup; instead of ignore your pivot index of array.

void quickSort(int *arr, int inf, int sup){
    if(arr){
        if(inf < sup){
            int pivot = partition(arr, inf, sup);
            //printf("pivot = %d", pivot);
            quickSort(arr, inf, pivot);
            quickSort(arr, pivot+1, sup);
        }
    }
}

Hope it can help. Thanks