Path: ...!feed.opticnetworks.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
Newsgroups: comp.lang.c
Subject: Re: Baby X is bor nagain
Date: Fri, 21 Jun 2024 11:19:10 +0200
Organization: A noiseless patient Spider
Lines: 17
Message-ID: <v53gie$33k73$1@dont-email.me>
References: <v494f9$von8$1@dont-email.me> <v4c8s4$1lki1$4@dont-email.me>
 <20240613002933.000075c5@yahoo.com> <v4emki$28d1b$1@dont-email.me>
 <20240613174354.00005498@yahoo.com> <v4okn9$flpo$2@dont-email.me>
 <20240617002924.597@kylheku.com> <v4pddb$m5th$1@dont-email.me>
 <20240618115650.00006e3f@yahoo.com> <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> <86y16zhcy3.fsf@linuxsc.com>
 <v51mvd$2lhe2$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 21 Jun 2024 11:19:11 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="017bd53d5809bfe07afbcdbc63488ddf";
	logging-data="3264739"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18gfwQVqIck8s54/1h5M+3fj5aBQ4tQz+Q="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.0
Cancel-Lock: sha1:oz8hbASd0EMNVIzHICHQheic2+I=
Content-Language: en-GB
In-Reply-To: <v51mvd$2lhe2$1@dont-email.me>
Bytes: 2550

On 20/06/2024 18:56, Malcolm McLean wrote:

> Yes, a qsort written in the natural way can getstuck if a sub0array it 
> considered sorted becmes not sortted on the next pass.

I have no idea what you might think of as the "natural" way to implement 
qsort.  But if it were, as the name implies, a quicksort, then it would 
not get stuck.  At each step, progress is always made - even with a 
comparison function that gave random values, you'd still have a worst 
case complexity of O(n²).

The only sorting algorithm I can think of that might get stuck with a 
slightly broken comparison function would be a poor bubblesort 
implementation that is run over the whole array every round, simply 
repeating until no changes are made in a round.