Quicksorting an array of pointers to structs

Question

I'm currently attempting to use the built-in quicksort provided by C in order to sort an array of pointers to structs. I want to sort each element based on a name element within the struct.

Although my debug output of the entire array each time through the comparison function shows me that the function is indeed shifting elements, the end result is not the correct sorted order. Is there something I'm just not seeing here?

typedef struct // The custom data type.
{
    char *name;
} Person;

----------------------------

Person **people; // A dynamically allocated array of Person pointers.
int numPeople;   // The logical index of people.
int maxPeople;   // The current maximum capacity of people.

int compare(const void *a, const void *b) // The comparison function for determining
{                                         //    alphabetic ordering.
   const Person *const *p1 = a;
   const Person *const *p2 = b;
   return strcmp((*p1)->name, (*p2)->name); // Compare alphabetically, return result.
}

void SomeFunction(void)
{
    qsort(people, numPeople, sizeof(Person *), compare); // Perform the sort.
}

Thanks for help with this.

Just to confirm that qsort is finding the correct data: you could add a printf line to compare to print the names of each person. If the result is not as expected, it's possible that *a and *b aren't pointers to Person objects after all. — Edmund
– Edmund, Commented Nov 28, 2012 at 1:25
I just did that and indeed it's printing out names that correspond to structs, so I guess that part is correct. Thanks for the suggestion. — Kris H.
– Kris H., Commented Nov 28, 2012 at 1:42

shinkou · Accepted Answer · 2012-11-28 01:49:01Z

1

I have tested your code and it looks working OK. Here is the code I compiled with gcc 4.5.2:

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

typedef struct // The custom data type.
{
        char *name;
} Person;

Person **people; // A dynamically allocated array of Person pointers.
int numPeople;   // The logical index of people.
int maxPeople;   // The current maximum capacity of people.

int compare(const void *a, const void *b) // The comparison function for determining
{                                         //    alphabetic ordering.
        const Person *const *p1 = a;
        const Person *const *p2 = b;
        return strcmp((*p1)->name, (*p2)->name); // Compare alphabetically, return result.
}

void SomeFunction(void)
{
        qsort(people, numPeople, sizeof(Person *), compare); // Perform the sort.
}

int main()
{
        int iCnt;

        maxPeople = 4;
        numPeople = 4;

        people = calloc(1, sizeof(Person *) * maxPeople);

        people[0] = calloc(1, sizeof(Person));
        people[1] = calloc(1, sizeof(Person));
        people[2] = calloc(1, sizeof(Person));
        people[3] = calloc(1, sizeof(Person));

        people[0]->name = strdup("Tanya");
        people[1]->name = strdup("Alfred");
        people[2]->name = strdup("Harry");
        people[3]->name = strdup("Oakley");

        for(iCnt = 0; iCnt < numPeople; iCnt ++)
                printf("[%d] %s\n", iCnt, people[iCnt]->name);

        SomeFunction();

        for(iCnt = 0; iCnt < numPeople; iCnt ++)
                printf("[%d] %s\n", iCnt, people[iCnt]->name);

        return 0;
}

The code looks legit and I'm not sure what's wrong. Could you try compiling the code I tested and see if it works?

answered Nov 28, 2012 at 1:49

shinkou

5,1351 gold badge24 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Kris H. Over a year ago

It turns out that I had some data corruption going on in a setter within the file that the Person was typedef'd in. So, the code actually does work fine now that I cleaned that up. Thanks for all of the effort that you guys put into helping me!

shinkou Over a year ago

@KrisH. I'm glad that you've found out the real cause. :)

Anon · Accepted Answer · 2012-11-28 01:29:18Z

0

Can you try with this

int compare(const void *a, const void *b) // The comparison function for determining
{                                         //    alphabetic ordering.
   const Person *p1 = *(const Person**)a;
   const Person *p2 = *(const Person**)b;
   return strcmp((p1)->name, (p2)->name); // Compare alphabetically, return result.
}

answered Nov 28, 2012 at 1:29

Anon

2,6766 gold badges28 silver badges39 bronze badges

2 Comments

Kris H. Over a year ago

I'm actually getting the same result that I got with that original code. From first element to last element, I'm getting Tanya, Alfred, Harry, Oakley after the sorting....

Daniel Fischer Over a year ago

No surprise, apart from the const qualifications, that's equivalent.

Collectives™ on Stack Overflow

Quicksorting an array of pointers to structs

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related