qsort in c not sorting my array of structs

Question

I'm having an issue with my comparison function for qsort. I've got an array, mGames, of type ListEntry. ListEntry looks like this:

struct ListEntry
{
    bool mLocal;
    int  mLastTurnTime;
};

That's actually rather oversimplified, there's more data in there but it's not being used in the sorting so I omitted it. Anyway, I'm trying to make it so that entries that have mLocal set to true are ordered first. Problem is, I can't get qsort to order my array whatsoever. Here's the comparison function:

int compare(const void* a, const void* b)
{
    ListEntry* e1 = (ListEntry*)a;
    ListEntry* e2 = (ListEntry*)b;
    if (e1->mLocal && e2->mLocal)
        return 0;
    return e1->mLocal ? -1 : 1;
}

and my call to it:

qsort(mGames, mNumGames, sizeof(ListEntry), compare);

where mNumGames is the number of games in the array (7 in my current test case), and mGames is defined as:

ListEntry mGames[MAX_GAMES]; // where MAX_GAMES is 50

When I step into the compare method, e1 and e2 contain their data as expected (as in, I'm not accessing garbage memory or didn't dereference things right).

The weird thing is, no matter how I change that comparison method, I can't get the order to change at all. I must be overlooking something really obvious.

Is the by-value assignment in your comparator accidental? You should not dereference the pointer but assign the result of the cast to another pointer. And I guess we need more code. — pmr
– pmr, Commented Oct 6, 2011 at 23:53
Ah, good call. I've changed it in my code to just use the pointer value and not be dereferenced. — RhomburVernius
– RhomburVernius, Commented Oct 6, 2011 at 23:57
By the way, is this C (tag, use of qsort) or C++ (no struct keyword in variable declaration, bool, cast of void pointer)? In the former case it must be some strange extensions (I know C99 has bool, but direct struct usage without struct keyword?) and in the latter case, don't use qsort anyway, use std::sort. — Christian Rau
– Christian Rau, Commented Oct 7, 2011 at 0:20

jpalecek · Accepted Answer · 2011-10-07 00:03:39Z

4

Your function is not a partial ordering. This

if (e1.mLocal && e2.mLocal)
    return 0;

should be in fact

if (e1.mLocal == e2.mLocal)

The point is, once you deal with qsort (and other sorting routines as well, you need to ensure the comparison relation is transitive and antisymmetric. That wouldn't be true in your case.

BTW, since you effectively sort only in two classes, it might be faster just to move the elements with .mLocal == 1 to the beginning of the array by something like

ListEntry *first = beginning of the array, *last = end of the array;
while(first < last) {
  if(!first->mLocal && last->mLocal)
    swap(first, last); // swap the two elements
  if(first->mLocal) first++;
  if(!last->mLocal) last --;
}

edited Oct 7, 2011 at 0:03

answered Oct 6, 2011 at 23:54

jpalecek

47.9k7 gold badges105 silver badges147 bronze badges

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

1 Comment

RhomburVernius Over a year ago

Ah, so it turns out the main problem was that I wasn't updating where my list elements were to be drawn at AFTER I had qsort them: I forgot that I was assigning where they appear on screen before the qsort. Turns out that was the real gist of the problem, though thanks for everyone's suggestions here, those were also part of a larger problem.

Collectives™ on Stack Overflow

qsort in c not sorting my array of structs

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related