Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Janis Papanagnou Newsgroups: comp.lang.c Subject: Re: challenge (simplyfying quicksort code) Date: Thu, 28 Mar 2024 13:03:45 +0100 Organization: A noiseless patient Spider Lines: 78 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit Injection-Date: Thu, 28 Mar 2024 12:03:47 +0100 (CET) Injection-Info: dont-email.me; posting-host="155435c3f40053ae5c3f5cbd325b2209"; logging-data="3751502"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/FC8I/TODdcpVUIuRclQZ/" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 Cancel-Lock: sha1:tbhchRkUAewKFesXJN8bBEX38HA= X-Enigmail-Draft-Status: N1110 In-Reply-To: Bytes: 4081 On 27.03.2024 12:04, fir wrote: > the chellenge is simplify such quicksort code as far as you can > > conditions > 1) it should work proper way > 2) should be not slower or only slightly slower > (so thsi is not optimistation for speed its more for being simple but > staing reasonably fast) > 3) by simplify i mean maybe removing soem if or some other > element but not necassary rewriting names for shorter etc as names are > not much meaningfull here (so by simplifying i mainy understand > removing something or some recomposition for something better/clearer) > 4) the basic quicksort has two calls inside this one is > opitmised to have only one , i think both versions are okay > but maybe thsi one with one call inside is maybe better > > > void QuicksortInts7(int* table, int lo, int hi) > { > > int i=lo; int j=hi; > > while (i { > int pivot =table[(lo+hi)/2]; > while (i<=j) // Partition > { > while (table[i] while (table[j]>pivot) j--; > if (i<=j) > { > int t=table[i];table[i]=table[j];table[j]=t; > i++; j--; > } > } > > if (lo < j){ QuicksortInts7(table, lo, j);} //recursion > lo=i; j=hi; > } > } > > > is there a way to simplify this? Your conditions listed above appear to be quite fuzzy and I think your view of "simplification" is a very subjective one, so it's probably impossible to provide an answer that suits you. But I can give you my own opinions below oriented on some keywords/conditions you used... Simplicity is something that keeps the intention of the algorithm clear, so I'd stay with two QS() calls, as in the original algorithm. (Your point 4.) Your algorithm has worst complexity O(N^2), so it's quite meaningless to speak about "slightly slower" or "reasonable fast". (Your point 2.) If folks want some speed guarantee then they'd enhance the algorithm by well established means[*] (which would require more code, though, so likely goes against your "challenge"). I wouldn't trust any home-brewed algorithm, especially if (as in this case) you changed or omitted conditions from the original algorithm. (See your own follow-up in this thread.) The least required would be the preconditions stated (e.g. is 'hi' the index of the last element in the table or the subsequent element). And the code should have sufficient comments to be able to work on it, in the first place. So given that "it should work proper way" is hard to [easily] verify. (Your point 1.) PS: I would suggest that you try to formally or analytically verify whether your variant is working correctly. (Or check it with *lots* of test data.) Janis [*] For example, the Pascal code of the CDC mainframe library I used 40 years ago already had median-of-3 pivot selection, and linear sort implemented for data partition subsets of less than 10 elements.