CODEWITHSUNDEEP
c
abc xyz
abc xyz

Reputation: 129

Sort an array of pointers in C

So I have a custom data type 'Medicine'. I also created an array where I store not instances of this data type, but pointers to instances of this data type. So each element from the array points to an instance of the data type. I want to sort this array using the name of each medicine. I have already done it using a selection sort that I wrote, but I'm trying to do it using the qsort function, so that I shorten the code. The problem is that I can't figure out how to write the compare function which I need to pass to the qsort function. It's not as easy as usual, since as I said I don't have instances in the array but rather pointers to instances of the array. This is the code that I wrote:

int compare(const void *a, const void *b) {
    Medicine *m1 = *((Medicine **) a);
    Medicine *m2 = *((Medicine **) b);
    if (strcmp(get_medicine_name(m1), get_medicine_name(m2)) < 0) {
        return 1;
    }
    return -1;
}

void sort_medicine_descending_name(DynamicArray *meds) {
    qsort(meds, get_dynamic_array_size(meds), sizeof(Medicine*), compare);
}

When I run this code I get a segmentation fault. I am positive that I don't have bugs in other parts of my code since I have quite a few other functions and they all work fine. I think my problem is when I try to cast and dereference those void pointers (although I am not sure). My logic behind it went something like this: Since I have pointers to Medicine in my array I need to type cast the arguments a and b as pointer to pointer, and then dereference them so that I get the pointers to Medicine. But since it didn't work, my intuition was clearly wrong. I'm still not fully competent when it comes to working with pointers, so I don't really know why this is not right, nor what I should do instead.

This is my implementation for Dynamic Array:

typedef struct {
    int capacity;
    int size;
    void **elems;
} DynamicArray;

I create instances of this dynamic array using the following "constructor":

DynamicArray *create_dynamic_array(int capacity) {
    DynamicArray *da = (DynamicArray *) malloc(sizeof(DynamicArray));
    da->capacity = capacity;
    da->size = 0;
    da->elems = (void**) malloc(sizeof(void*) * capacity);
    return da;
}

The way I wanted to write it is so that a dynamic array can store any type of elements. That's why da->elems is a pointer to pointer of void. This way I can just store the pointer to any data type in the dynamic array. So I can store the meds in a dynamic array by storing pointers to instances of Medicine (which, by the way, is also dynamically allocated). da->capacity is the capacity of the dynamic array, and whenever the array gets filled the capacity increases. da->size is the current number of elements in the dynamic array, which increases whenever I add an element to it and decreases whenever I remove an element.

I get the size of the dynamic using the following function:

int get_dynamic_array_size(DynamicArray *da) {
    return da->size;
}

Finally, the "class" Medicine stores, among other things, a dynamically allocated char array where the name is stored. get_medicine_name() takes as argument a pointer to medicine and returns the pointer to this char array.

Upvotes: 0

Views: 177

Answers (1)

vlad_tepesch
vlad_tepesch

Reputation: 6925

The problem of your code is, that qsort assumes that it gets an array of equal types. But you pass your root structure to that. So your compare function gets the size and capacity member as the pointer, that surely cause a segfault.

Instead you should pass the elem array.

qsort(meds->elem, meds->size, sizeof(*meds->elem), compare);

Upvotes: 1

Related Questions