Message-ID: <388758A7.1B64BDF9@cyberoptics.com>
From: Eric Rudd <rudd AT cyberoptics DOT com>
Organization: CyberOptics
X-Mailer: Mozilla 4.08 [en] (Win95; U)
MIME-Version: 1.0
Newsgroups: comp.os.msdos.djgpp
Subject: Re: qsort() bug?  Or invalid usage???
References: <R0Gh4.2371$Ll5 DOT 3502 AT news2 DOT randori DOT com> <867gpd$k0u$1 AT nets3 DOT rz DOT RWTH-Aachen DOT DE>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 28
Date: Thu, 20 Jan 2000 12:49:11 -0600
NNTP-Posting-Host: 38.196.93.9
X-Trace: client 948394160 38.196.93.9 (Thu, 20 Jan 2000 13:49:20 EST)
NNTP-Posting-Date: Thu, 20 Jan 2000 13:49:20 EST
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Hans-Bernhard Broeker wrote:

> The bigger worry, however, is the following: is this really a valid
> comparison function? I.e. does it define an ordering of the input
> elements? I haven't analysed it completely, but I doubt it does.
> It has to be guaranteed to fulfill the following rules for the
> 'smaller than' relation it describes:
>
>         IF a<b and b<c   THEN a<c
>         NEVER a<b and b<a, at the same time

Yes, and equal objects must return 0.  The last time I checked, DJGPP's qsort
implementation sometimes attempts to dereference beyond the ends of the array
if the comparison function returns inconsistent results.  I don't think that a
good implementation should do this, but I can find nothing in the ANSI standard
that would prohibit such behavior.

Unfortunately, it is often difficult to verify that the comparison function is
consistent in the sense described above.  For example, I ran into this very
problem once when I attempted to sort an ASCII file based on the floating-point
values of the numbers stored therein.  It seems that the optimizer stored one
result of atof() in a temporary "double" variable, and left the other in the
coprocessor to long-double precision, with the result that two equal values
sometimes compared unequal.  This kind of thing may be giving trouble here.

-Eric Rudd
rudd AT cyberoptics DOT com