question abourt sort

teisen · 07-01-2009, 08:47 PM

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?

itCbitC · 07-01-2009, 09:26 PM

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.

MK27 · 07-01-2009, 09:31 PM

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.

teisen · 07-01-2009, 10:06 PM

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?

MK27 · 07-01-2009, 10:24 PM

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.

tabstop · 07-01-2009, 10:25 PM

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.

MK27 · 07-01-2009, 10:50 PM

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, 11:00 PM

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!");

teisen · 07-02-2009, 04:05 AM

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?

MK27 · 07-02-2009, 07:04 AM

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.

teisen · 07-02-2009, 07:20 AM

>>MK27

thank you very much. ^.^)

07-01-2009, 08:47 PM	#1
teisen Registered User Join Date: Jul 2009 Posts: 4	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? Last edited by teisen; 07-02-2009 at 05:33 PM.*
teisen is offline

07-01-2009, 09:31 PM	#3
MK27 subminimalist Join Date: Jul 2008 Location: NYC Posts: 3,944	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. __________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS Last edited by MK27; 07-01-2009 at 09:41 PM.
MK27 is offline

07-01-2009, 10:06 PM	#4
teisen Registered User Join Date: Jul 2009 Posts: 4	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? Last edited by teisen; 07-01-2009 at 10:32 PM.
teisen is offline

07-02-2009, 07:20 AM	#11
teisen Registered User Join Date: Jul 2009 Posts: 4	>>MK27 thank you very much. ^.^)
teisen is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How to sort a simple linked list using swap-sort method	JOCAAN	C Programming	24	08-07-2009 11:48 AM
Straight Insertion Sort function problem	StaticKyle	C++ Programming	6	05-12-2008 04:03 AM
Bubble Sort, Qucik Sort	insomniak	C Programming	2	03-15-2003 04:54 PM
Radix Sort question	ripper079	C++ Programming	5	01-06-2003 06:58 AM
question about Quick Sort	Liberty4all	C++ Programming	8	11-23-2002 10:38 AM