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<hi)
{
int pivot =table[(lo+hi)/2];
while (i<=j) // Partition
{
while (table[i]<pivot) 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?

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<hi)
> {
> int pivot =table[(lo+hi)/2];
> while (i<=j) // Partition
> {
> while (table[i]<pivot) 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?

beciuse there is like repetition

> while (i<=j)
> if (i<=j)

it seems that mayeb thsi could be reduced to one but its to hard for
me ..thsi quicksort transformation is damn hard - some logical knot
(at elast when im not much in form)

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<hi)
> {
> int pivot =table[(lo+hi)/2];
> while (i<=j) // Partition
> {
> while (table[i]<pivot) 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.

Janis Papanagnou wrote:
> 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<hi)
>> {
>> int pivot =table[(lo+hi)/2];
>> while (i<=j) // Partition
>> {
>> while (table[i]<pivot) 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.
>
this above (as far as i remember as i was working ion this quite five
years above was outcome of my transformation of somw quicksort i find in net

yesyerday and dey before yesterday i tried to write better version
strightforward begoning from the idea but failed - so many littel e
things amkes something is wrong and i failed

note the idea is not hard you got soem partition of numbers

1 20 3 200 33 3 38 38 29 30

something liek that and you get the "pivot" from the middle
it would be 33

having such pivot you consider the values to be bigger (B)
or less (L) here

L L L B LB L B B L L

you come from two both begining and end and find rot B's on the left and
L's from teh right if you met them you swap it

L L L (B) LB L B B L (L)

into

L L L (L) LB L B B L (B)

then you continue until the left and right pointers met
but the met condition in the middle is herd to do properly for some reason

i slightly cant belive i find the version abowe which seem to be correct
(though im not sure if it has no bug as those whiles do not check for
limit so im not sure if it will not go off partition but felt to weary
to check it)

but the chellenge is if for example thise comparsion i met couldnt be
reduzed while(i<-j) if (i<=j)

but somewhat hart it is this primal c which is notably harder than
normal c coding