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.

Realize

data should be declared const. – Templin

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

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]. – Templin

Answer 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**.

Conservative

Answer 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.

Journeyman

Answer 3

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 **.

Collaborative

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. – Realize

@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. – Isobaric

Answer 4

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 **.

Renata

Answer 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.

Zante

Answer 6

from man qsort:

The  contents of the array are sorted in ascending 
order according to a comparison function pointed to by
compar, which is called with two arguments that **point**
to the objects being compared.

So it sounds like the comparison function gets pointers to the array elements. Now a pointer to a char * is a char ** (i.e. a pointer to a pointer to a character).

Focal

Answer 7

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

is a statement asking the compiler for an array of size 5 of character pointers. You have initialized those pointers to string literals, but to the compiler, it's still an array of five pointers.

When you pass that array into qsort, the array of pointers decays into a pointer pointing to the first element, in accordance with C array parameter passing rules.

Therefore you must process one level of indirection before you can get to the actual character arrays containing the constants.

Templin

Answer 8

@bodacydo here is a program that may explain what other programmers are trying to convey but this would be in context of "integers"

#include <stdio.h>


int main()
{
    int i , j;
    int *x[2] = {&i, &j};

    i = 10; j = 20;

    printf("in main() address of i = %p, address of j = %p \r\n", &i, &j);

    fun(x);
    fun(x + 1);

    return 0;
}


void fun(int **ptr)
{
    printf("value(it would be an address) of decayed element received = %p, double dereferenced value is %d \r\n",*ptr, **ptr);
    printf("the decayed value can also be printed as *(int **)ptr = %p \r\n", *(int **)ptr );
}

Coenosarc

Answer 9

qsort() passes a pointer to the user-defined comparison function and as you have a char * (pointer to char array) hence your comparison function should dereference from pointer to pointer hence char **.

Silky