Re: Baby X is bor nagain

Ben Bacarisse <ben@bsb.me.uk> writes:

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>

Ben Bacarisse <ben@bsb.me.uk> writes:
>

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>
[on the requirements for qsort]
>

I certainly would favor improved wording that made this clearer.
In fact, simply explicitly mandating total ordering rather than
making a vague comment about consistency would probably be the
best approach.

>
Clearly the C standard intends to impose a weaker requirement
than that the comparison function be a total ordering.

>
The plot thickens.  Unless, of course, you are referring to the
distinction you drew before between an ordering of all possible objects
and only those in the array.

>
Consider the following situation.
>
We have an array with seven elements, the integers 1 to 7,
in that order.  We call qsort on the array, with a natural
comparison function that compares the integer values.
>
The qsort function starts with a check, and for any array
with eight elements or fewer a simple insertion sort is
done.  Because 1 is less than 2, these elements stay
where they are.  Because 2 is less than 3, there is only
the one comparison, and 3 stays where it is.  And so on...
at each point in the sort an element is compared to the
one before it, and nothing changes.  Six compares are
done to sort seven elements.  Question:  has the program
encountered any undefined behavior?  (I expect you will
say no.)
>
Now consider a second situation.
>
We again have an array with seven elements, the integers 1
to 7, but not necessarily in order.  We call the same
qsort function.  This time though the argument for the
comparison function is for a function that just always
returns -1.  The same sequence of events takes place as
did in the first situation:  each element after the first
is compared to the one before it, and because the previous
element is deemed "less than" this element no movement
occurs and we proceed to the next element of the array.
Six compares are done to "sort" seven elements.  Question:
has the program encountered any undefined behavior?
>
If there has been undefined behavior, which passages in
the C standard explains the difference relative to the
first situation?
>
If there has not been undefined behavior, what does that
say about what the requirements are for a call to qsort?

>
So you are pointing out that only the comparisons made have to be
"consistent with one another"?  BTW, your function that returns -1 is
just the total extension of my partial "dog order" function.

Let me try to be clear here.  As I read the C standard:  whatever
we decide "consistent with" means, it is only the results of the
calls to the comparison function that were actually performed
that matter.  If other calls to the comparison function would
have given a result not consistent with the results of calls that
/were/ performed, but those other calls were not performed, that
potential inconsistency doesn't make the behavior be undefined.

It makes sense to me that this rule is what was intended.  Whatever
results qsort gets back, as long as they are consistent with one
another the sorting algorithm is going to work okay, in the sense
that it won't rely on contradictory information.  Conversely, if
qsort does get back contradictory information, then it easily might
wander off into the weeds and do who knows what.  So the condition
for undefined behavior matches those cases where qsort could be
confused by having received bogus results.