Path: ...!3.eu.feeder.erje.net!feeder.erje.net!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben@bsb.me.uk>
Newsgroups: comp.lang.c
Subject: Re: Baby X is bor nagain
Date: Tue, 25 Jun 2024 01:35:36 +0100
Organization: A noiseless patient Spider
Lines: 66
Message-ID: <877cedoo4n.fsf@bsb.me.uk>
References: <v494f9$von8$1@dont-email.me> <v4rv0o$1b7h1$1@dont-email.me>
	<20240618184026.000046e1@yahoo.com> <v4sd75$1ed31$1@dont-email.me>
	<877celzx14.fsf@nosuchdomain.example.com>
	<v4u85k$1t2pu$2@dont-email.me> <v4ucmn$1u14i$1@dont-email.me>
	<v4v2br$22c0m$1@dont-email.me> <v4v5nu$230rh$2@dont-email.me>
	<v4vfrn$24rv6$1@dont-email.me> <v50n9s$2fkko$1@dont-email.me>
	<v50poh$2g4ha$1@dont-email.me> <87iky3svqh.fsf@bsb.me.uk>
	<874j9nxsdy.fsf@nosuchdomain.example.com> <874j9ns382.fsf@bsb.me.uk>
	<86h6dlhb34.fsf@linuxsc.com> <8734p3rjno.fsf@bsb.me.uk>
	<v59bhe$ch8p$1@dont-email.me> <86zfrbfsd6.fsf@linuxsc.com>
	<875xtzp9vl.fsf@bsb.me.uk> <865xtyfxdr.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Tue, 25 Jun 2024 02:35:37 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b2e0149f9e88712508ba5999d7ddf609";
	logging-data="1265544"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18vhGIV/4AESFe+EuLWk0i+Jos/XGpmm30="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:/HsnjcK3Vv7aZP7qi6CEidSL66E=
	sha1:PeEa+Tb4ive2grZZKSZXBNNJeXY=
X-BSB-Auth: 1.9bdc0bb9072d975bd7c5.20240625013536BST.877cedoo4n.fsf@bsb.me.uk
Bytes: 4410

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.

-- 
Ben.