Background
Years ago I had a solution for the subject problem, but I deleted it when I started using C++ and the STL and didn't need to worry about it any more. However, I now help with a large Open Source project (
BRL-CAD), the core of which is still programmed in C (and likely to remain so). Consequently, I recently needed to use qsort on a heap array of pointers and the nightmare cropped up again.
Once more I tried to find a good example that worked and couldn't. All the examples I found used arrays on the stack and they didn't use arrays of pointers. Eventually, I found the solution through some grunt testing and trial and error. I hope someone can use my example now.
The code
#include
#include
#include
const int debug = 0;
/* Define an array of critters to sort. */
typedef struct crit
{
const char* name;
int index;
} crit_t;
const crit_t dat[] =
{
{"Gonzo", 3},
{"Fozzie", 3},
{"Kermit", 1},
{"Piggy", 2},
{"Sam", 3},
#if 0
{"Robin", 6},
{"Animal", 8},
{"Camilla", 8},
{"Sweetums", 9},
{"Dr. Strpork", 10},
{"Link Hogthrob", 11},
{"Zoot", 12},
{"Dr. Honeydew", 13},
{"Beaker", 14},
{"Swedish Chef", 15},
#endif
};
const int ncrits = sizeof(dat)/sizeof(crit_t);
// the sort functions MUST have this signature
int
crit_index_sort(const void* p1, const void* p2)
{
// cast args into the desired type
const crit_t* c1 = *(crit_t**)p1;
const crit_t* c2 = *(crit_t**)p2;
// now do comparisons
if (c1->index < c2->index)
return -1;
else if (c1->index > c2->index)
return +1;
else
return strcmp(c1->name, c2->name);
}
int
crit_name_sort(const void* p1, const void* p2)
{
// cast args into the desired type
const crit_t* c1 = *(crit_t**)p1;
const crit_t* c2 = *(crit_t**)p2;
// now do comparisons
if (debug) {
printf("DEBUG: comparing %s and %s\n", c1->name, c2->name);
}
int ncmp = strcmp(c1->name, c2->name);
if (ncmp) {
return ncmp;
}
else if (c1->index < c2->index)
return -1;
else if (c1->index > c2->index)
return +1;
else
return 0;
}
int
main(int argc, char** argv)
{
int i;
// an array from the heap
crit_t** muppets = (crit_t**)malloc(sizeof(crit_t*) * ncrits);
// fill it
for (i = 0; i < ncrits; ++i) {
crit_t* c = (crit_t*)malloc(sizeof(crit_t));
c->name = strdup(dat[i].name);
c->index = dat[i].index;
muppets[i] = c;
}
// show it
printf("\nUnsorted array:\n");
for (i = 0; i < ncrits; ++i) {
printf(" %2d %s\n", muppets[i]->index, muppets[i]->name);
}
// output
#if 0
Unsorted array:
3 Gonzo
3 Fozzie
1 Kermit
2 Piggy
3 Sam
#endif
// alpha sort
qsort(muppets, ncrits, sizeof(crit_t*), crit_name_sort);
// show it
printf("\nSorted by name:\n");
for (i = 0; i < ncrits; ++i) {
printf(" %2d %s\n", muppets[i]->index, muppets[i]->name);
}
// index sort
qsort(muppets, ncrits, sizeof(crit_t*), crit_index_sort);
// output
#if 0
Sorted by name:
3 Fozzie
3 Gonzo
1 Kermit
2 Piggy
3 Sam
#endif
// show it
printf("\nSorted by index:\n");
for (i = 0; i < ncrits; ++i) {
printf(" %2d %s\n", muppets[i]->index, muppets[i]->name);
}
// output
#if 0
Sorted by index:
1 Kermit
2 Piggy
3 Fozzie
3 Gonzo
3 Sam
#endif
}
(to be continued)
