Qsort inaccuracy?

Discussion in 'C Programming' started by No Such Luck, Dec 14, 2004.

  1. No Such Luck

    No Such Luck Guest

    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;
    }
     
    No Such Luck, Dec 14, 2004
    #1
    1. Advertising

  2. No Such Luck

    Eric Sosman Guest

    No Such Luck wrote:
    > 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

    --
     
    Eric Sosman, Dec 14, 2004
    #2
    1. Advertising

  3. No Such Luck

    Ben Pfaff Guest

    "No Such Luck" <> writes:

    > 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;
    }
    --
    "I hope, some day, to learn to read.
    It seems to be even harder than writing."
    --Richard Heathfield
     
    Ben Pfaff, Dec 14, 2004
    #3
  4. No Such Luck

    CBFalconer Guest

    No Such Luck wrote:
    >
    > 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.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Dec 14, 2004
    #4
  5. In article <>,
    CBFalconer <> wrote:

    >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
     
    Richard Tobin, Dec 14, 2004
    #5
  6. No Such Luck wrote:
    > 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."
     
    Martin Ambuhl, Dec 14, 2004
    #6
  7. On Tue, 14 Dec 2004 18:15:49 +0000, Richard Tobin wrote:

    > In article <>,
    > CBFalconer <> wrote:
    >
    >>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?


    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
     
    Lawrence Kirby, Dec 14, 2004
    #7
  8. On 14 Dec 2004 07:05:28 -0800, "No Such Luck" <>
    wrote:

    >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;
    }


    --
    Robert B. Clark (email ROT13'ed)
    Visit ClarkWehyr Enterprises On-Line at http://www.3clarks.com/ClarkWehyr/
     
    Robert B. Clark, Dec 14, 2004
    #8
  9. No Such Luck

    Eric Sosman Guest

    Robert B. Clark wrote:
    >
    > 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);

    --
     
    Eric Sosman, Dec 14, 2004
    #9
  10. CBFalconer <> writes:
    > 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.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Dec 14, 2004
    #10
  11. In article <> "No Such Luck" <> writes:
    ....
    > 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?
    --
    dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
    home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
     
    Dik T. Winter, Dec 15, 2004
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dennis Benzinger

    timeit.repeat() inaccuracy on W2K?

    Dennis Benzinger, Nov 25, 2003, in forum: Python
    Replies:
    1
    Views:
    344
    Raymond Hettinger
    Nov 26, 2003
  2. Brian Quinlan
    Replies:
    1
    Views:
    326
    Dieter Maurer
    Jun 16, 2006
  3. alf
    Replies:
    2
    Views:
    340
    Paul Rubin
    Sep 4, 2006
  4. No Such Luck

    Qsort inaccuracy?

    No Such Luck, Dec 14, 2004, in forum: C Programming
    Replies:
    3
    Views:
    410
    Al Bowers
    Dec 14, 2004
  5. lorlarz
    Replies:
    8
    Views:
    144
    lorlarz
    Aug 20, 2008
Loading...

Share This Page