[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Undefined qsort behavior



Katie Lucas wrote:
On Thu, Dec 05, 2002 at 02:44:55PM -0200, Miguel A. Osorio wrote:


material/texture). But the qsort man page says: "If  two  members
compare as equal, their order in the sorted array is undefined". So my
question is this: this "undefined order" still groups equal elements
together, or is the undefined *really* undefined ? For instance, if I
have an array: 4 2 3 1 2 4, do I *always* get: 1 2 2 3 4 4 ?

"Undefined" has a very technical defintion. It means, very literally,
the behaviour has not been specified in ANY WAY and the routine is
free to do as it pleases with it.

It could vary between library implementations, between machines with
different CPUs, it could vary on initial conditions, sizes of the
arrays; absolutely ANYTHING. And when it does so, you have no
comeback.

Testing it on your machine and using that undefined bahaviour is
asking for it not to work somewhere else later. You might as well
raise the bug against that bit of code yourself.

Undefined means "don't use this, it might stop working like it does at
any point in time".
In this context, it most definitely means:

   The order of two or more elements for which the 'compar' function
   returns zero - are undefined RELATIVE TO EACH OTHER.

...and not "completely undefined".

The man page may be poorly worded - but any system whose qsort does not
return a sorted result (eg 1 3 2 2 instead of 1 2 2 3) would result in a
non-functioning machine in pretty short order.

I can't think of any case where I've seen Qsort being used where the
author of the comparison function took the time to ensure that it
never returns zero...which is what is implied by this concern.  The
man page would be FAR more strongly worded if that were the case.

What this means is that if you have:

     APPLES    1
     ORANGES   2
     LEMONS    2
     BANANAS   3

...you *MAY* get:

   APPLES, ORANGES, LEMONS, BANANAS

...but at random, you might get....

   APPLES, LEMONS, ORANGES, BANANAS

...but you'll NEVER get:

   LEMONS, APPLES, ORANGES, BANANAS

...just because 'compar(LEMONS,ORANGES)==0'.

For *sure*.

---------------------------- Steve Baker -------------------------
HomeEmail: <sjbaker1@airmail.net>    WorkEmail: <sjbaker@link.com>
HomePage : http://web2.airmail.net/sjbaker1
Projects : http://plib.sf.net    http://tuxaqfh.sf.net
           http://tuxkart.sf.net http://prettypoly.sf.net