question abourt sort

Printable View

07-01-2009
teisen

question abourt sort

I have some codes below which i think are to implement array sort. But no idea about what "x" ,"y" (particularly codes //1, //2, //3,)are used for.
who can help?

Code:

void sort(int *p1, int p2) { ............ }

Also, what I really want to know how much time complexity has been increased compared to normal bubble sort?
07-01-2009
itCbitC

Quote:

Originally Posted by teisen

I have some codes below which i think are to implement array sort. But no idea about what "x" ,"y" (particularly codes //1, //2, //3,)are used for.
who can help?

Those "codes" are C++ style "comments" and this array sort looks like a very obfuscated implementation of bubble sort. Search these forums for good examples of coding bubble sort.
07-01-2009
MK27

It better be obfuscated*. If I wasn't aware that this was just supposed to be a sort, I might have tried harder to figure it out. This is the line that bugs me:

Code:

y = temp+x || temp == ++x;

Can you use || in place of else here?
This one just seems screwed up:

Code:

x = y + *p1 - *(p1+j+1);

This is a very bad example to try and learning sorting from. As itCbitC says, it is probably a bubblesort which uses a flag (t) as an optimization. I'm pretty sure this one is actually very unoptimal in other ways, ie there are too many operations going on.

*obfuscated code is code written intentionally to be difficult or impossible for someone other than the author to understand. In this case it's mostly just the one letter variables.
07-01-2009
teisen

thanks a lot for your answers,itCbitC and MK27

I only got code body actually, the function name "sort" was given by myself as i guessed that might be trying to implement array sort (bubble sort ). I have been particularly concerned about those "obfuscated code"
like

Code:

x = y + *p1 - *(p1+j+1); y = temp+x || temp == ++x;

as I was wondering if they might be trying to implement some other functions or have some particular use as well which i wasn't aware of.

Plus, as i have mentioned above, I want to know how much time complexity has been increased?
07-01-2009
MK27

Quote:

Originally Posted by teisen

as I was wondering if they might be trying to implement some other functions or have some particular use as well which i wasn't aware of.

Sorting arrays is "very well explored territory"; it is probably impossible, at this point in time, that someone is going to come forward with some kind of new and revolutionary sorting method. It's all done and finished; all you have to do is learn the established methods.

Which means most of the material you will find should reflect this available "state of the art". All you have to do is learn the basic form of the algorithms. It might be a good idea to look at *both* pseudo code descriptions *and* actual C implementations. So pseudo-code for a modified bubblesort might be:

Code:

while (1) { // eg, an infinite loop set flag to 0 for (i=0; i<the lenght of the array; i++) { compare i to i+i; if i+1 is less than i, swap the values and add 1 to flag } if the flag is still 0, break out of the loop because the array is sorted. }

The key here is to set the flag to 0 at the beginning of the while loop, before you iterate thru the array again.

IMO bubblesort is the easiest and most "intuitive" -- that's what I did off the top of my head without knowing anything about sorting, and somebody told me it was a bubblesort. Other people have said the same thing about "selection sort". Insertion sort is pretty straight forward too.

Merge sort is quite a bit trickier. And don't bother with "quick sort" until you understand merge sort.
07-01-2009
tabstop

Quote:

Originally Posted by MK27

It better be obfuscated*. If I wasn't aware that this was just supposed to be a sort, I might have tried harder to figure it out. This is the line that bugs me:

Code:

y = temp+x || temp == ++x;

Can you use || in place of else here?

|| means "or". So temp+x is evaluated. If it is nonzero, then we are done, because or short-circuits. If, however, temp+x is zero, the right-hand side is evaluated, meaning x is incremented. y is assigned the value of 1 whenever temp <> -x or x == temp-1, and 0 otherwise. [Edit: I should be clearer: I mean "or" in the PERL sense, "open(file) or die(trying)" -- it's where the idea came from after all.]

Quote:

Originally Posted by MK27

This one just seems screwed up:

Code:

x = y + *p1 - *(p1+j+1);

Not sure what you're complaining about here. *p1 = p1[0] just like *(p1+j+1) = p1[j+1].

Quote:

Originally Posted by MK27

This is a very bad example to try and learning sorting from.

No kidding. I'm here because I have completely failed at falling asleep and I still don't want to try to follow that code.
07-01-2009
MK27

Quote:

Originally Posted by tabstop

|| means "or". So temp+x is evaluated. If it is nonzero, then we are done, because or short-circuits. If, however, temp+x is zero, the right-hand side is evaluated, meaning x is incremented. y is assigned the value of 1 whenever temp <> -x or x == temp-1, and 0 otherwise. [Edit: I should be clearer: I mean "or" in the PERL sense, "open(file) or die(trying)" -- it's where the idea came from after all.]

Thanks for that one tabstop. I notice that

Code:

1 || puts("This won't happen!");

is valid C code, which I would never have thought of trying.

>>Not sure what you're complaining about here. *p1 = p1[0]

I think I've "in one ear and out the other'd" this about 5 times now, probably because I perpetually use the subscripted form.
07-01-2009
ಠ_ಠ

Quote:

Originally Posted by MK27

Code:

1 || puts("This won't happen!");

is valid C code, which I would never have thought of trying.

The thought has occurred to me, but that's probably because my instructor was very clear that if the first one is true then the others won't be evaluated. also && could be used to make it a little more obfuscated

Code:

!1 && puts("This won't happen!");
07-02-2009
teisen

Quote:

Originally Posted by MK27

Sorting arrays is "very well explored territory"; it is probably impossible, at this point in time, that someone is going to come forward with some kind of new and revolutionary sorting method. It's all done and finished; all you have to do is learn the established methods.

many thanks,MK27

so do you mean x, y related code here like

Code:

x = y + *p1 - *(p1+j+1); y = x?++x:x-2; y = temp+x || temp == ++x;

doesn't do any good at all other than messing up?

In addition, if i want to optimize this function and make it go faster, i will have nothing to do but choose other sort algorithm, like merge sort. right?
07-02-2009
MK27

Quote:

Originally Posted by teisen

so do you mean x, y related code here like

doesn't do any good at all other than messing up?

Okay, I took a closer look at that and it really is an example of obfuscated code. One simple "obfuscating" technique is to add in things that are totally irrelevant to what is actually going on. I compiled this and fed it a random array of ints, and it does sort them properly. However, if I comment out the lines in red below, it still does *exactly* the same thing, meaning about half of this code is just obfuscation:

Code:

for (; j<i; x++, z++) { if (*(int*)(p1+j) > *(int*)(p1+z)) { // x = y + *p1 - *(p1+j+1); //1 temp = *(p1+j); *(p1+j) = *(p1+j+1); //2 // y = x?++x:x-2; *(p1+j+1) = temp; t=1; // if (x > y) // y = temp+x || temp == ++x; //3 } ++j; }

The (int*) cast on the third line is totally unnecessary too, since those are already *int! If you look at the lines that are not commented out, you should be able to recognize the bubblesort algorithm.

Quote:

In addition, if i want to optimize this function and make it go faster, i will have nothing to do but choose other sort algorithm, like merge sort. right?

Yes, merge sort is exponentially faster with long lists. If you are only expecting to sort a few hundred items, it does not make too much difference.
07-02-2009
teisen

>>MK27

thank you very much. ^.^)