Qsort inaccuracy?

[No Such Luck]

Hi All:

The code below (using the qsort function) produces the following
incorrect result. The last two numbers are not sorted. It this
innaccurate result specific to my compiler's qsort, or is there a bug
in my code? Thanks...

Original Array:
3.125420
8.618710
4.220840
2.181950
8.852060
1.763020
0.164010

Sorted Array:
0.164010
1.763020
2.181950
3.125420
4.220840
8.852060
8.618710

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

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

typedef int (*qsortfunc) ( const void*, const void* );


int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

int main ()
{

int i;
double array[7];
array[0] = 3.12542;
array[1] = 8.61871;
array[2] = 4.22084;
array[3] = 2.18195;
array[4] = 8.85206;
array[5] = 1.76302;
array[6] = 0.16401;

printf ("\nOriginal Array:\n");

for (i = 0; i < 7; i++)
printf ("%lf\n", array);

qsort(array, 7, sizeof(double),(qsortfunc) compare_doubles);

printf ("\nSorted Array:\n");
for (i = 0; i < 7; i++)
printf ("%lf\n", array);


return 1;
}

 

[Eric Sosman]

Hi All:

The code below (using the qsort function) produces the following
incorrect result. The last two numbers are not sorted. It this
innaccurate result specific to my compiler's qsort, or is there a bug
in my code? Thanks...
[...]
int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

This comparison function returns zero if two numbers
differ by less than one. It will consider 7.9 and 8.1 as
equal, because the difference (0.2 or -0.2) becomes zero
when converted from double to int.

This could cause qsort() to go completely off the rails,
since the comparison function would report that 7.9 == 8.8,
8.8 == 9.7, 9.7 == 10.6 and so on, but would also report
that 7.9 < 10.6. That's an inconsistent result, and if you
give qsort() inconsistent results from comparisons all Hell
may break loose.

There's another problem, too:

typedef int (*qsortfunc) ( const void*, const void* );
[...]
qsort(array, 7, sizeof(double),(qsortfunc) compare_doubles);

I suspect you inserted the cast to silence the compiler's
complaint about using the wrong type of function. Please
get out of that habit: Silencing a complaint is not the same
as curing the complained-about problem, and in this case the
original problem is still there in all its gory glory. You
haven't put out the fire, you've merely removed the batteries
from the smoke alarm. Sleep in peace ...

The comparison function for qsort() must *be* a function
that takes two `const void*' pointers as arguments. Mere
pretense is not enough; you will get away with it on many
machines, but your masquerade will not fool them all -- and
when it fails to fool them, the failure is likely to be
spectacular. See Question 13.9 in the comp.lang.c Frequently
Asked Questions (FAQ) list

http://www.eskimo.com/~scs/C-faq/faq.html

 

[Ben Pfaff]

int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

int
compare_doubles (const void *a_, const void *b_)
{
const double *a = a_;
const double *b = b_;

return *a < *b ? -1 : *a > *b;
}

 

[CBFalconer]

The code below (using the qsort function) produces the following
incorrect result. The last two numbers are not sorted. It this
innaccurate result specific to my compiler's qsort, or is there
a bug in my code? Thanks...
.... snip ...

int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

You should indent your code, using spaces, not tabs. At any rate,
your compare function is faulty, unless you expect all doubles that
are withing 1.0 of each other to be considered equal. Try:

int compare_double(const void *a, const void *b)
{
const double *left = a, *right = b;

return (left > right) - (left < right);
}

qsort neither knows nor cares what types are being compared, and
thus uses void* pointers. Your compare function, on the other
hand, does now the type of the comparees, and must impost that.
The common use of (a - b) in such a function runs into overflow
problems for ints, and other more subtle problems for reals. The
construct above uses the automatic 1 or 0 boolean value of
relations to ensure the +1, 0, or -1 are returned.

 

[Richard Tobin]

At any rate,
your compare function is faulty, unless you expect all doubles that
are withing 1.0 of each other to be considered equal.

Would such a function be legal for qsort() even if he expected that?
It would give 1.2 == 2.0 and 2.0 == 2.8 but not 1.2 == 2.8. I can't
see anything in the C89 standard requiring the comparison function to
be consistent in that respect, but the meaning of the term "ascending
order" is not clear if it is not.

-- Richard

 

[Martin Ambuhl]

Hi All:

The code below (using the qsort function) produces the following
incorrect result. The last two numbers are not sorted. It this
innaccurate result specific to my compiler's qsort, or is there a bug
in my code?

There is a bug in your code:

8.852060
8.618710

int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

This is hopeless. Whenever the difference of doubles being compared is
less than 1.0 your function says they are equal. This is what is called
"being too clever by half."

 

[Lawrence Kirby]

Would such a function be legal for qsort() even if he expected that?

I would say not. In practical terms this will break real qsort()
implementations and I don't see that such implementations are
obviously inconsistent with the standard.

It would give 1.2 == 2.0 and 2.0 == 2.8 but not 1.2 == 2.8. I can't
see anything in the C89 standard requiring the comparison function to
be consistent in that respect, but the meaning of the term "ascending
order" is not clear if it is not.

The whole concept of a comparison sort i.e. generating an ordering based
on comparisons is meaningless if the comparison function doesn't produce a
consistent ordering. The only special case of this where element that
compare equal may end up in any order w.r.t. to each other IS covered
explicitly by C89, and that's not an issue with the comparison function
itself.

Lawrence

 

[Robert B. Clark]

The code below (using the qsort function) produces the following
incorrect result. The last two numbers are not sorted. It this
innaccurate result specific to my compiler's qsort, or is there a bug
in my code? Thanks...

The latter. Read on...

int
compare_doubles (const double *a, const double *b)
{

Insert here:
printf(" %f - %f = % d\t(% f)\n", *a, *b, (int)(*a-*b), (*a-*b));

return (int) (*a - *b);
}

<snip>

When run, you'll note that your compare_doubles() function reports the
difference between 8.85206 and 8.61871 as zero instead of the expected
0.23335. This really shouldn't be unexpected, since you do explicitly
cast the return value to an int.

I'd rewrite your compare_doubles() as follows:

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

int compare_doubles(const void *p1, const void *p2)
{
const double *a = p1;
const double *b = p2;

printf(" %f - %f = % d\t(% f)\n", *a, *b, (int)(*a-*b), (*a-*b));

/* We don't really care about a==b, given the precision used here */

if (*a - *b > 0)
return 1;
else
return -1;
}


#define NUM 7

int main(void)
{
int i;
double array[NUM] =
{
3.12542, 8.61871, 4.22084, 2.18195, 8.85206, 1.76302, 0.16401
};

printf ("\nOriginal Array:\n");
for (i = 0; i < NUM; i++)
printf ("%f\n", array);

qsort(array, NUM, sizeof(array[0]), compare_doubles);

printf ("\nSorted Array:\n");
for (i = 0; i < NUM; i++)
printf ("%f\n", array);


return 1;
}

 

[Eric Sosman]

I'd rewrite your compare_doubles() as follows:

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

int compare_doubles(const void *p1, const void *p2)
{
const double *a = p1;
const double *b = p2;

printf(" %f - %f = % d\t(% f)\n", *a, *b, (int)(*a-*b), (*a-*b));

/* We don't really care about a==b, given the precision used here */

if (*a - *b > 0)
return 1;
else
return -1;
}

This is not valid if there is any possibility that
equal values can appear in the array, because the results
of comparison would be inconsistent: For equal A and B
the comparator would claim both A>B and A<B, and this
inconsistency could send qsort() 'round the bend. For
equal values, the comparator must return zero.

An idiom I've always found pretty (but that some
beginners may have difficulty deciphering) is

return (*a > *b) - (*a < *b);

 

[Keith Thompson]

No Such Luck wrote: [snip]

int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}

You should indent your code, using spaces, not tabs. At any rate,
your compare function is faulty, unless you expect all doubles that
are withing 1.0 of each other to be considered equal.

It's faulty regardless of what you expect. As others have pointed out
elsewhere in this thread, it doesn't give a consistent ordering, which
causes undefined behavior.

Try:

int compare_double(const void *a, const void *b)
{
const double *left = a, *right = b;

return (left > right) - (left < right);
}

I think you mean

return (*left > *right) - (*left < *right);

qsort neither knows nor cares what types are being compared, and
thus uses void* pointers. Your compare function, on the other
hand, does now the type of the comparees, and must impost that.
The common use of (a - b) in such a function runs into overflow
problems for ints, and other more subtle problems for reals. The
construct above uses the automatic 1 or 0 boolean value of
relations to ensure the +1, 0, or -1 are returned.

Note that the comparison function is allowed to return any positive
value if left > right, and any negative value if left < right.
Returning just -1, 0, or +1 is certainly ok, but it's not required.

 

[Dik T. Winter]

> The code below (using the qsort function) produces the following
> incorrect result. The last two numbers are not sorted. It this
> innaccurate result specific to my compiler's qsort, or is there a bug
> in my code? Thanks...

There is a bug in your code.

> 8.618710
> 8.852060 ....
> int
> compare_doubles (const double *a, const double *b)
> {
> return (int) (*a - *b);
> }

What do you think the return value is when a == 8.618710 and b == 8.852060?