🚀 go-pugleaf

jkb@mrc-lmb.cam.ac.uk (James Bonfield) writes:

|Are there any limitations on what the sort function passed over to qsort can
|do or return? I know it's meant to return < 0, 0 or > 0 for the various
|compare operations, but which you return is purely up to your own comparison
|system.

|On tracking down a bug in some old code I noticed that we had the
|compare function returning something like "a > b" instead of "b - a".
|Now this is obviously some silly bug in our coding, but "a > b" is still
|a valid sort function surely? The reason I ask is that this that such
|functions appear to make the Irix 5.3 qsort() function underflow the
|passed array. Please check the following function to verify that I
|haven't done something daft.

As others have pointed out, b - a runs the risk of overflow if a and b
are large enough in magnitude and of opposite sign.  That's why it is
often recommended against as a value to return from the compare function.
BTW, without overflow, b - a is positive if b > a, not if a > b.


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

|static int sort_func(const void *pa, const void *pb)
|{
|    const int *a = (int *)pa;
|    const int *b = (int *)pb;

|    return *a > *b;
|}

This function returns either a 0 if *a <= *b or a 1 if *a > *b.  Since
keys are considered equal if sort_func() returns zero, this will not
properly discern a case where the first argument must appear before
the second.  It would surprise me not at all if qsort() relied on
sort_func() having the property that

	!!sort_func(p1, p2) == -1 * !!sort_func(p2, p1)

which does not hold for this function.  (The Standard wording seems
to me to require this property, but I'm not a duly certified language
lawyer...)

Try 

	static int sort_func(const void *pa, const void *pb)
	{
	    const int *a = (int *)pa;
	    const int *b = (int *)pb;

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

instead.
-- 
		Matthew Saltzman
		Clemson University Math Sciences
		mjs@clemson.edu