How to qsort an array of pointers to char in C?

Question

Suppose I have an array of pointers to char in C:

char *data[5] = { "boda", "cydo", "washington", "dc", "obama" };

And I wish to sort this array using qsort:

qsort(data, 5, sizeof(char *), compare_function);

I am unable to come up with the compare function. For some reason this doesn't work:

int compare_function(const void *name1, const void *name2)
{
    const char *name1_ = (const char *)name1;
    const char *name2_ = (const char *)name2;
    return strcmp(name1_, name2_);
}

I did a lot of searching and found that I had to use ** inside of qsort:

int compare_function(const void *name1, const void *name2)
{
    const char *name1_ = *(const char **)name1;
    const char *name2_ = *(const char **)name2;
    return strcmp(name1_, name2_);
}

And this works.

Can anyone explain the use of *(const char **)name1 in this function? I don't understand it at all. Why the double pointer? Why didn't my original function work?

Thanks, Boda Cydo.

Solution 1

If it helps keep things straight in your head, the type that you should cast the pointers to in your comparator is the same as the original type of the data pointer you pass into qsort (that the qsort docs call base). But for qsort to be generic, it just handles everything as void*, regardless of what it "really" is.

So, if you're sorting an array of ints, then you will pass in an int* (converted to void*). qsort will give you back two void* pointers to the comparator, which you convert to int*, and dereference to get the int values that you actually compare.

Now replace int with char*:

if you're sorting an array of char*, then you will pass in a char** (converted to void*). qsort will give you back two void* pointers to the comparator, which you convert to char**, and dereference to get the char* values you actually compare.

In your example, because you're using an array, the char** that you pass in is the result of the array of char* "decaying" to a pointer to its first element. Since the first element is a char*, a pointer to it is a char**.

Solution 2

Imagine your data was double data[5] .

Your compare method would receive pointers (double*, passed as void*) to the elements (double).
Now replace double with char* again.

Solution 3

The comparison function takes pointers to the type of object that's in the array you want to sort. Since the array contains char *, your comparison function takes pointers to char *, aka char **.

Solution 4

qsort is general enough to sort arrays consisting of other things than pointers. That's why the size parameter is there. It cannot pass the array elements to the comparison function directly, as it does not know at compile time how large they are. Therefore it passes pointers. In your case you get pointers to char *, char **.

Solution 5

Maybe it is easier to give you an code example from me. I am trying to sort an array of TreeNodes and the first few lines of my comparator looks like:

int compareTreeNode(const void* tt1, const void* tt2) {
   const TreeNode *t1, *t2;
   t1=*(const TreeNode**)tt1;
   t2=*(const TreeNode**)tt2;

After that you do your comparison using t1 and t2.

View more solutions

Comments

[Billy ONeal]

data should be declared const.

[bodacydo]

Billy, if it's const, can it be still sorted?

[Billy ONeal]

Yes. The array can be non const, but the pointers contained within that array should be const. You're not allowed to modify compile-time constant literals like that (it's undefined behavior to do so). To get that, you want const char *data[5]. If you want the array itself to be constant too, then you'd do const char * const data[5].

[bodacydo]

I don't understand, sorry. The first argument to qsort is a *. I pass a **. Which means I effectively pass just one *. But one * is exactly a char *. See? That's why I am confused.

[jamesdlin]

@bodacydo: The important point is the comparison function takes pointers to elements of the array. Since each element of your array is a pointer-to-char, the comparison function operates on pointers-to-pointers-to-char.