Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #27579

Re: How to apply qsort() with a parameter?

Show all headers | View raw

On 10/23/2012 10:28 AM, Scott Fluhrer wrote:
> "Eric Sosman" <esosman@comcast-dot-net.invalid> wrote in message
> news:k6441n$oa7$1@dont-email.me...
>> On 10/22/2012 1:51 PM, none Rouben Rostamian wrote:
>>> How does one apply qsort() if the comparison criterion
>>> depends on a parameter?
>>>
>>> Specifically, suppose I wish to sort an array of int,
>>> according to distance from a prescribed value `n':
>>>
>>> int compar(const void *aa, const void *bb)
>>> {
>>>           int a = *(int *)aa;
>>>           int b = *(int *)bb;
>>>           return abs(a - n) < abs(b - n);
>>
>>      Aside: This can't be right, as it doesn't define
>> a total ordering.
>>
>
> I believe this point could use some expansion.  What Eric was refering to
> was the fact that a qsort implementation expects a comparison function that
> returns negative if the first element should appear earlier than the second
> element, positive if the second element should appear earlier, and 0 if you
> don't care.  In particular, if compare(a, b) returns positive, compare(b, a)
> must return negative.

     Exactly.  Also, if compare(a,b) and compare(a,c) both return
zero, then compare(b,c) must return zero.  It's easy to see that
the function as shown doesn't satisfy this.  (Consider n=0 for
simplicity, then compare(10,1) and compare(10,5) both return zero,
but compare(1,5) returns one.)

> If the above isn't true, well, I don't know if there is any requirement on
> what qsort is allowed to do.  The most obvious thing it could do in this
> case is not sort the array as you expect (for example, given the array [1000
> 1] and N=0, it may leave the array undisturbed).  Other misbehaviors (such
> as infinite looping, or returning an array which is not a permutation of the
> original, or simply crashing) are less likely, but are still conceivable.

     As far as I can see, the behavior is undefined.  The "shall
be consistent" requirement is in 7.22.5, which is not part of a
constraint. 4p2 tells us that violating a non-constraint "shall"
yields undefined behavior.

     As to outcomes, both crashes and infinite loops seem likely
possibilities to me.  For example, a qsort() using the Quicksort
algorithm with Sedgewick's median-of-three heuristic may well
walk off one end or the other of the array if the comparator
misbehaves and fails to stop it.  Even if this doesn't loop or
crash, it might exchange some array elements with bytes outside
the array limits.

     That's another reason to keep comparators simple: It's
easier to verify their correctness.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How to apply qsort() with a parameter? rouben@shadow.(none) (Rouben Rostamian) - 2012-10-22 17:51 +0000
  Re: How to apply qsort() with a parameter? ImpalerCore <jadill33@gmail.com> - 2012-10-22 11:18 -0700
    Re: How to apply qsort() with a parameter? ImpalerCore <jadill33@gmail.com> - 2012-10-22 11:26 -0700
    Re: How to apply qsort() with a parameter? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-10-22 20:27 +0100
  Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-22 11:38 -0700
  Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 14:41 -0400
    Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 14:59 -0400
      Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-22 13:25 -0700
        Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 16:54 -0400
          Re: How to apply qsort() with a parameter? Robert Wessel <robertwessel2@yahoo.com> - 2012-10-22 23:25 -0500
            Re: How to apply qsort() with a parameter? James Kuyper <jameskuyper@verizon.net> - 2012-10-23 07:42 -0400
            Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 08:14 -0400
          Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-23 07:05 -0700
            Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 10:13 -0400
    Re: How to apply qsort() with a parameter? "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2012-10-23 10:28 -0400
      Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 10:56 -0400
  Re: How to apply qsort() with a parameter? Öö Tiib <ootiib@hot.ee> - 2012-10-22 15:30 -0700
  Re: How to apply qsort() with a parameter? rouben@shady.(none) (Rouben Rostamian) - 2012-10-23 03:52 +0000
    Re: How to apply qsort() with a parameter? Keith Thompson <kst-u@mib.org> - 2012-10-22 22:46 -0700
      Re: How to apply qsort() with a parameter? pete <pfiland@mindspring.com> - 2012-10-23 16:03 -0400
    Re: How to apply qsort() with a parameter? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-10-23 06:43 -0700

csiph-web