This is the mail archive of the newlib@sources.redhat.com mailing list for the newlib project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: BUG: qsort reorders elements in already sorted array


Corinna Vinschen wrote:

Hi,

I found that there's a bug in newlib's implementation of qsort, which
results in more or less unreliable reordering of things.

The problem seem to occur in border cases only.  The border case I
have is tin, the news reader.  I've build the latest developer version
of tin, 1.5.18, and found that the ordering of threads in a newsgroup
was correct, except to my surprise that the first and the last thread
had exchanged their place.  As a figure, the order wasn't

0 1 2 3 4 5 6 7 8 9

but

9 1 2 3 4 5 6 7 8 0

This happened in all newsgroups, except for one, which had only 7 articles.



It sounds like you want to sort by more than one key. Why not have your compare function actually do that. This way, the undefined qsort results are not relevant.

struct info
{
   int score;
   int date; /* or article number, etc. */
};

int
compare (void *v1, void *v2)
{
   struct info *i1 = v1, *i2 = v2;

if (v1->score - v2->score) /* Maybe you want v2 - v1 */
return v1->score - v2->score; /* Scores are different, so ignore date. */
else
return v1->date - v2->date; /* Scores are same, so use date. */
}


James





Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]