| Deutsch English Français Italiano |
|
<86o77pdwpb.fsf@linuxsc.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!feed.opticnetworks.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch <tr.17687@z991.linuxsc.com> Newsgroups: comp.lang.c Subject: Re: Baby X is bor nagain Date: Tue, 25 Jun 2024 05:38:08 -0700 Organization: A noiseless patient Spider Lines: 82 Message-ID: <86o77pdwpb.fsf@linuxsc.com> References: <v494f9$von8$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> <877cedoo4n.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Tue, 25 Jun 2024 14:38:11 +0200 (CEST) Injection-Info: dont-email.me; posting-host="df40ff635303007d0403e8efc320894e"; logging-data="1649053"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19AM2TBd8YiLwjCFjrJpWbduVfDWhp+CxA=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:QB03wvyJ1LC7sBrk7uKG8eOopX8= sha1:Em9oRMAvqQPM637L/WuXy5/f4Rs= Bytes: 5379 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.