Thread: question abourt sort

  1. #1
    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.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by teisen View Post
    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.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    Last edited by MK27; 07-01-2009 at 09:41 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    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.

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by teisen View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MK27 View Post
    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 View Post
    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 View Post
    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.
    Last edited by tabstop; 07-01-2009 at 10:32 PM.

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by tabstop View Post
    || 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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    Quote Originally Posted by MK27 View Post
    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!");
    Last edited by ಠ_ಠ; 07-01-2009 at 11:07 PM.
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  9. #9
    Registered User
    Join Date
    Jul 2009
    Posts
    4
    Quote Originally Posted by MK27 View Post
    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?

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by teisen View Post
    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.

    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    Registered User
    Join Date
    Jul 2009
    Posts
    4
    >>MK27

    thank you very much. ^.^)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM
  4. Radix Sort question
    By ripper079 in forum C++ Programming
    Replies: 5
    Last Post: 01-06-2003, 06:58 AM
  5. question about Quick Sort
    By Liberty4all in forum C++ Programming
    Replies: 8
    Last Post: 11-23-2002, 10:38 AM

Tags for this Thread