Sorting an array of struct pointers using qsort

Question

I'm getting weird results from trying to use qsort on this array of structs.

I have this struct:

struct access_data{
    int sector;
    int arrival_time;
    int checked;
    int processed;
};

I construct an array of access_data pointers from a file such that they are sorted by arrival_time, but I need to sort them by sector later, so I have the following:

int compare_data(const void* a, const void* b){
    if (((access_data*)a)->sector < ((access_data*)b)->sector)
        return 1;
    else if (((access_data*)a)->sector > ((access_data*)b)->sector)
        return -1;
    else
        return 0;
}

void scan(access_data* data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data*), &compare_data);

    show_data(data, len);
}

show_data simply prints the data, but I get the following on a sample input; again, sorted already by arrival time:

data[0]: arrival_time: 7, sector: 3
data[1]: arrival_time: 6, sector: 8
data[2]: arrival_time: 5, sector: 6
data[3]: arrival_time: 4, sector: 5
data[4]: arrival_time: 3, sector: 12
data[5]: arrival_time: 2, sector: 10
data[6]: arrival_time: 1, sector: 1
data[7]: arrival_time: 0, sector: 2

It is simply not sorting by sector, but by reverse arrival time. I'm really at a complete loss at to what could be causing this behavior.

Bonnette

Please post a minimal test-case. – Bixler

Answer 1

Your code suggests that you are actually trying sort an array of pointers to struct.

In this case you are missing a level of indirection. You also have your directions reversed.

Your compare_data routine would be fine for reverse sorting an array of structs, but you wish to sort an array of pointers based on what they point to.

int compare_pointed_to_data(const void* a, const void* b) {
    // a is a pointer into the array of pointers
    struct access_data *ptr_to_left_struct = *(access_data**)a;
    struct access_data *ptr_to_right_struct = *(access_data**)b;

    if ( ptr_to_left_struct->sector < ptr_to_right_struct->sector)
        return -1;
    else if (ptr_to_left_struct->sector > ptr_to_right_struct->sector)
        return 1;
    else
        return 0;
}

Oecd

Answer 2

The problem here is that you are telling QSort to sort an array of pointers, and as a result the parameters in the comparator are pointers to pointers.

int compare_data(const void* _a, const void* _b){
    access_data *a = *(access_data**)_a, *b = *(access_data**)_b;
    if ((a)->sector < (b)->sector)
        return 1;
    else if ((a)->sector > (b)->sector)
        return -1;
    else
        return 0;
}

void scan(access_data* data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data*), &compare_data);

    show_data(data, len);
}

Let me know if you still have any questions

Hebetic

Answer 3

Mistake 1

printf("size=%d",sizeof(access_data*));

prints 4, expected: 16. This was the biggest problem: sorting 8 times 4 bytes, not 8 times 16.

Weirdness 2

qsort() expects a pointer-to-data but scan() receives a pointer-to-pointer-to data. Recommended fix:

void scan(access_data data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data), &compare_data);
    show_data(data, len);
}

Optimization 3

Your compare_data() is equal to

int compare_data(const void* a, const void* b){
    return ((access_data*)b)->sector - ((access_data*)a)->sector;
}

My full working program:

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

struct access_data {
    int sector;
    int arrival_time;
    int checked;
    int processed;
};
typedef struct access_data access_data;
void show_data(access_data*data, int len) {
        printf("Showing size = %d", sizeof(access_data*));
        for (int i = 0;i < len; i++) { 
            printf("data[%d]: arrival_time: %d, sector: %d\n",i,data[i].arrival_time,data[i].sector);
        }
}

int compare_data(const void* a, const void* b){
        return ((access_data*)b)->sector - ((access_data*)a)->sector;
}
int compare_data1(const void* a, const void* b){
    if (((access_data*)a)->sector < ((access_data*)b)->sector)
        return 1;
    else if (((access_data*)a)->sector > ((access_data*)b)->sector)
        return -1;
    else
        return 0;
}

void scan(access_data data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data), &compare_data);

    show_data(data, len);
}

int main() {
        printf("START\n");
        access_data data[8] = {
                { 3, 4, 5, 6 },
                { 2, 1, 5, 5 },
                { 1, 1, 3, 6 },
                { 4, 4, 5, 4 },
                { 5, 4, 3, 4 },
                { 6, 2, 5, 6 },
                { 7, 2, 5, 4 },
                { 0, 4, 5, 6 }
        };
        scan(data, 8, 0);
}

Comeaux

OP is passing an array of pointers to the function scan(). It would be incorrect to assume he can easily change parts of the code. – Lelialelith

@self In the text he says "array of structs". That is what I wrote. We don't see his code. – Comeaux

void scan(access_data* data[] – Lelialelith