CODEWITHSUNDEEP
carrayslistsorting
Mutai Mwiti
Mutai Mwiti

Reputation: 487

Which is faster, sorting an array of structs or sorting a list of structures C?

I am faced with a challenge. I have data on a linked list of structs. Do l move the data onto an array of structs then sort it using qsort() or do l use merge sort? This is the struct:

struct properties{
    char *path;
    char *name;
    char *extension;
    long int size;
    long unsigned created;
    long unsigned modified;
    long unsigned access;
    int permissions;
};

Upvotes: 2

Views: 284

Answers (1)

Klas Lindbäck
Klas Lindbäck

Reputation: 33283

I would create an array of pointers to the structs and sort the pointer array using qsort. Using pointers instad of copying the entire structs will use less memory.

Create a comparator like this:

int propertyComparator(const void *s1, const void* s2) {
    struct property *p1 = (struct property *)s1, *p2 = (struct property *)s2;

    /* compare p1 and p2, below is just an example */
    int result = strcmp(p1->name, p2->name);
    return result;
}

Call it like this:

 struct property *array;
 /* add code to allocate and create array */
 qsort(array, num_elements, sizeof array, propertyComparator);

Edit:

If you want to have a sorted linked list, mergesort is about as fast. Seems it depends on how fragmented the linked list is. See https://stackoverflow.com/a/1525419/646887

The reason I prefer qsort is that it is part of the C lib, so I don't have to write and maintain so much code. And it is always a fast choice.

Upvotes: 3

Related Questions