I’ll confess that when I use a quicksort to sort and array of strings, I don’t use the C Library’s qsort() function. No, I write my own. The problem is that when sorting an array of strings, the qsort() function’s compar argument is a pain in the butt to craft properly.

An array of strings is an array of pointers. Because an array itself is a pointer, the end result is a pointer to a pointer, or the ugly ** thing, which I’ve written about elsewhere on this site.

The beauty of the pointer array is that the strings themselves aren’t messed with; only the pointers are sorted (based on the strings). For the qsort() function, the problem is how to translate an array of pointers into something that the compare() function swallows in an obedient manner.

As a review, here is the pattern normally used in the compare() function:

int compare(const void *a, const void *b)
{
    return( *(type *)a - *(type *)b);
}

The function’s two arguments never change. They are const void types. const means that the variable’s value cannot change; it’s constant. void identifies the variables as pointers of a non-specific type. The variable is typecast properly within the function, typically within the return statement, as shown above.

With a pointer-to-a-pointer variable, you would think you could get away with something like the following to compare two strings:

    return( strcmp((char **)a,(char **)b) );

Alas, no: That doesn’t work. It’s essentially a stab in the dark — a good stab, close to the solution, but wrong.

The problem is the const keyword. The variables must still be treated as constants, so that keyword must be part of the solution. The typecast for an array of strings is correctly (char **), but that still doesn’t handle the fact that the strcmp() function needs pointers, not pointer-pointers. So another asterisk is required to make that function happy.

Yes, 10,000 monkeys sitting at keyboards with an abundance of asterisk keys would eventually divine a solution. Rather than wait that long, behold my solution, using similar code as presented in last week’s Lesson, but using pointer notation to create the array of strings:

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

#define C 15

int compare(const void *a, const void *b);

int main()
{
    char *crew[] = {
        "Thorin",   "Fili", "Kili",
        "Bilbo",    "Dori", "Balin",
        "Dwalin",   "Ori",  "Gloin",
        "Bifur",    "Nori", "Bofur",
        "Bombur",   "Oin",  "Gnadalf"
    };
    int x;

    /* print original strings */
    printf("Original: ");
    for(x=0;x<C;x++)
        printf("%s ",crew[x]);
    putchar('\n');

    /* quicksort the list */
    qsort(crew,C,sizeof(char *),compare);

    /* print sorted strings */
    printf("  Sorted: ");
    for(x=0;x<C;x++)
        printf("%s ",crew[x]);
    putchar('\n');

    return(0);
}

int compare(const void *a, const void *b)
{
    const char **pa,**pb;

    pa = (const char **)a;
    pb = (const char **)b;
    return( strcmp(*pa,*pb) );
}

To make the code in the compare() function more readable, I use two pointer-pointer variables, pa and pb. These are assigned the values of the two pointers passed to the function, a and b, both of which must be typecast to the ** thing; an array of pointers. (That’s what’s being sorted.)

Once pa and pb are assigned, they can then be used in the strcmp() function, nestled in the return statement. The pointer operator * is required inside the strcmp() function because array elements are being sorted, not the entire array, which is how the compiler sees a ** variable.

Yes, that’s confusing! Don’t feel bad if you’re intimidated by the entire thing.

Of course, my solution above is written for readability. You can reduce the compare() function to a single return statement, if you’re really crazy:

    return( strcmp( *((const char **)a), *((const char **)b)) );

I don’t fault anyone for not coming up with this solution on their own. It is not easy! But that’s the way it’s done. Even advanced C programmers write down stuff like this so that they don’t have to re-think the solution later.