is it about sorting?

[newer69]

Hello,
I need your help, Ive got a function and I consider it as a sort function but I am not sure about the type of sort and the complexity.
Moreover I cannot quite get what does exactly the "||" mean in the specific point of that function.
Thank you for any help

the function is:

void teest(int *prm1, int prm2)
{
  int m, n, x, y, z, tmp, flg;
  for(m=prm2-1; m>0; --m)
  {
    flg = 0;
    x = y = n = 0;
    z = 1;

    for (; n<m; x++, z++)
    {
      if (*(int*)(prm1+n) > *(int*)(prm1+z))
      {
        x = y + *prm1 - *(prm1+n+1);
        tmp = *(prm1+n);
        *(prm1+n) = *(prm1+n+1);
        y = x?++x:x-2;
        *(prm1+n+1) = tmp;
        flg=1;
        if (x > y)
          y = tmp+x || tmp == ++x;
      }
      ++n;
    }

    if (!flg)
      break;
  }
}

[Peter87]

It looks a bit like bubble sort to me, but it has some extra stuff so I'm not sure.

|| is logical or. It returns true if at least one of the sides are true. Any non-zero value will be treated as true, and zero as false so
y = tmp+x || tmp == ++x; can be written as y = tmp+x != 0 || tmp == ++x;
Note that if the left expression is true it will not evaluate the right expression, so if tmp+x != 0 then x will not be incremented.

[newer69]

I really dont get it.. What about if
tmp=3
x=2
then tmp+x=5 and tmp==++x
so what is the final value of y?
y should be an integer and not a boolean value as you can see..

thanks

[Peter87]

The code is obscure! Where did you get it?

y will have value 1 because true is 1 and false is 0.

[newer69]

I cant tell that there may be sth wrong here because I was given that as a test for a job so... dont you tell me that this is a trap :p

so taking what you said into consideration, y will always have either 0 or 1, right?

[Peter87]

So they gave you this at job interview. That makes more sense. They probably made the code unnecessary complicated just to see how you reasoned.

Looking more closely you see that the value of x and y is never actually used for anything other than changing the values of x and y so you can actually remove them completely from the program.

z is always one larger than n, so you can remove z and substitute z with n+1 on line 13.

[newer69]

thanks very much so the complexiy is o(n^2)
and the final code is sth like this:

void teest(int *prm1, int prm2)
{
  int m, n, tmp, flg;
  for(m=prm2-1; m>0; --m)
  {
    flg = 0;
    n=0;

    while(n<m)
    {
      if ( prm1[n] > prm1[n+1])
      {
        tmp = prm1[n];
        prm1[n] = prm1[n+1];
        prm1[n+1]= tmp;
        flg=1;
      }
      ++n;
    }

    if (!flg)
      break;
  }
}

as you can see there is already the optimization of the flag ..
Do you think that there is sth else that could make that algorithm (Bubble sort) better and faster? is there another better optimization?

thanks again :)