Comparison function in qsort()

[Spoon]

Hello,

I've come across the following comparison function used as the 4th
parameter in qsort()

int cmp(const void *px, const void *py)
{
const double *x = px, *y = py;
return (*x > *y) - (*x < *y);
}

It came "as-is" i.e. no comments.

Is it good style to write comparison functions that way?

Should the return values be made more explicit? Or would it be enough to
add comments explaining why the function (usually) works?

--
Regards, Spoon

[Richard Tobin]

In article <ln************ @nuthaus.mib.or g>,
Keith Thompson <ks***@mib.or g> wrote:

The code above, "return (*x > *y) - (*x < *y);", is also probably
better-behaved in the presence of infinities and NaNs, at least quiet
NaNs.

And this is just the sort of thing that many programmers will not be
aware of, so the lack of a comment is inexcusable.

-- Richard

[Dik T. Winter]

In article <e2***********@ pc-news.cogsci.ed. ac.uk> ri*****@cogsci. ed.ac.uk (Richard Tobin) writes:

In article <ln************ @nuthaus.mib.or g>,
Keith Thompson <ks***@mib.or g> wrote:

The code above, "return (*x > *y) - (*x < *y);", is also probably
better-behaved in the presence of infinities and NaNs, at least quiet
NaNs.

And this is just the sort of thing that many programmers will not be
aware of, so the lack of a comment is inexcusable.

What is better behaved? It depends on how the compiler works what is
returned in the case of NaNs, and it is not sure that what is returned
is also consistent. (And be aware that the comparison function must
be consistent, otherwise sorting can fail.) But it works well in the
case of infinities and when overflow occurs. Consider a compiler that
uses the compare greater instruction. If x is a NaN, both comparisons
will return false, and so the returned value is 0. Now when the
compiler uses the compare greater or uncomparable instruction, in that
case both comparisons return true, and the function will again return 0.
So with these scenarios the comparison function will tell a NaN is
equal to any other number.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Robert Latest]

On Tue, 18 Apr 2006 11:55:15 GMT,
Dik T. Winter <Di********@cwi .nl> wrote
in Msg. <Ix********@cwi .nl>

So with these scenarios the comparison function will tell a NaN is
equal to any other number.

....which is exactly as reasonable as making NaN greater or smaller than
any other number, or erratically switching between behaviors. I admit
the latter case is the worst because it's hard to debug, but in any case
an array with NaNs in it is unsortable by size anyway.

robert

[P.J. Plauger]

"Robert Latest" <bo*******@yaho o.com> wrote in message
news:4a******** ****@individual .net...

On Tue, 18 Apr 2006 11:55:15 GMT,
Dik T. Winter <Di********@cwi .nl> wrote
in Msg. <Ix********@cwi .nl>

So with these scenarios the comparison function will tell a NaN is
equal to any other number.
...which is exactly as reasonable as making NaN greater or smaller than
any other number,

Uh, no it's not. If the comparison function doesn't impose a strict
weak ordering on all values, a typical sort can loop or overwrite
storage. NaN should be either greater or less than any finite value,
comparing equal only to another NaN.
or erratically switching between behaviors. I admit
the latter case is the worst because it's hard to debug, but in any case
an array with NaNs in it is unsortable by size anyway.

Not true. If you're lucky, your compiler will either:

a) evaluate x != x as true for a NaN, or

b) supply some form of the C99 isnan(x) generic-function macro.

You comparison function is messier, but writable. And robust in the
presence of NaNs.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

[Robert Latest]

On Tue, 18 Apr 2006 09:43:22 -0400,
P.J. Plauger <pj*@dinkumware .com> wrote
in Msg. <X6************ *************** ***@giganews.co m>

You comparison function is messier, but writable. And robust in the
presence of NaNs.

After reading the C Standard and after a bit of thinking I decided
that you're right. A comparison function should compare NaNs greater or
smaller than any number, and comparison of two NaNs should evaluate as
equal.

robert