having trouble with this c quick sort while using an array struct

Question

The program doesn't crash, the build is successful, and it runs through the rest of main properly. The only problem is that the sort doesn't actually sort the array.

I left out the creation of the array and the rest of main simply because I've already tested them with another sort, and they work properly. However I'm supposed to use a higher level sort so I have to change things.

//struct for the array
typedef double darray_value_t;

typedef struct darray_t_tag {
    darray_value_t *data;
    size_t size;
    size_t capacity;
} darray_t;

//top of main
quickSort(&dataset, 0, dataset.size - 1);
//rest of main

//functions used to for the quick sort
void quickSort(darray_t *dataset, int lowValue, int highValue) {
    if (lowValue < highValue) {
        int part = partition(dataset, lowValue, highValue);

        quickSort(dataset, lowValue, part - 1);

        quickSort(dataset, part + 1, highValue);
    }
}

darray_value_t partition(darray_t *dataset, int lowValue, int highValue) {
    int pivot = dataset->data[highValue];

    int i = (lowValue - 1);

    for (int j = lowValue; j < highValue; j++) {
        if (dataset->data[j] <= pivot) {
            i++;
            swapValues(&dataset->data[i], &dataset->data[j]);
        }
    }

    swapValues(&dataset->data[i + 1], &dataset->data[highValue]);

    return (i + 1);
}

void swapValues(darray_value_t *a, darray_value_t *b) {
    darray_value_t temp = *a;
    *a = *b;
    *b = temp;
}

Answer 1

There are multiple problems in your code:

• the return value of partition should be int, not darray_value_t,

• conversely, the type of pivot should be darray_value_t, not int.

Here is a modified version:

#include <stdio.h>

//struct for the array
typedef double darray_value_t;

typedef struct darray_t_tag {
    darray_value_t *data;
    size_t size;
    size_t capacity;
} darray_t;

void swapValues(darray_value_t *a, darray_value_t *b) {
    darray_value_t temp = *a;
    *a = *b;
    *b = temp;
}

int partition(darray_t *dataset, int lowValue, int highValue) {
    darray_value_t pivot = dataset->data[highValue];
    int i = lowValue;

    for (int j = lowValue; j < highValue; j++) {
        if (dataset->data[j] <= pivot) {
            swapValues(&dataset->data[i++], &dataset->data[j]);
        }
    }
    swapValues(&dataset->data[i], &dataset->data[highValue]);

    return i;
}

//functions used to for the quick sort
void quickSort(darray_t *dataset, int lowValue, int highValue) {
    if (lowValue < highValue) {
        int part = partition(dataset, lowValue, highValue);

        quickSort(dataset, lowValue, part - 1);
        quickSort(dataset, part + 1, highValue);
    }
}

int main() {
    darray_value_t arr[] = { 2.0, 1.5, 4.5, -1 };
    darray_t dataset = { arr, 4, 4 };

    quickSort(&dataset, 0, dataset.size - 1);
    for (size_t i = 0; i < dataset.size; i++) {
        printf(" %g", dataset.data[i]);
    }
    printf("\n");
    return 0;
}