Path: csiph.com!news.swapon.de!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Baby X is bor nagain Date: Mon, 24 Jun 2024 03:28:16 -0700 Organization: A noiseless patient Spider Lines: 57 Message-ID: <865xtyfxdr.fsf@linuxsc.com> References: <20240618115650.00006e3f@yahoo.com> <20240618184026.000046e1@yahoo.com> <877celzx14.fsf@nosuchdomain.example.com> <87iky3svqh.fsf@bsb.me.uk> <874j9nxsdy.fsf@nosuchdomain.example.com> <874j9ns382.fsf@bsb.me.uk> <86h6dlhb34.fsf@linuxsc.com> <8734p3rjno.fsf@bsb.me.uk> <86zfrbfsd6.fsf@linuxsc.com> <875xtzp9vl.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Mon, 24 Jun 2024 12:28:19 +0200 (CEST) Injection-Info: dont-email.me; posting-host="b3b1304951eae8dc1e53ef86c96f1e35"; logging-data="945292"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ECVHGf2eYSRotm3ryDklrenqXo4nUMa8=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:T4l1l+ZL9Zpl5ATI6hICgYczzcE= sha1:nk2OTwYN6sN/XrNNMVu35kzS00Y= Xref: csiph.com comp.lang.c:386449 Ben Bacarisse writes: > Tim Rentsch writes: > >> James Kuyper 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?