CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11
  1. #1
    Join Date
    Nov 2011
    Posts
    2

    sorting algorithm

    Hi All, anyone knows the answer:

    If I have n intervals with start points stored in int* start and end points stored in int *end. I want to sort the start array but then reorder the end array according to the sorted array, e.g.
    {1, 4, 3} is my start
    {2, 5, 7} is my end
    each coordinates correspond to each other.

    then I sort the start to be {1, 3, 4} and I want the end to look like {2, 7, 5}.
    I can of course call the std::sort function on start, but how do I reorder the end?

  2. #2
    Join Date
    Apr 1999
    Posts
    27,449

    Post Re: sorting algorithm

    Quote Originally Posted by happybo7 View Post
    Hi All, anyone knows the answer:

    If I have n intervals with start points stored in int* start and end points stored in int *end. I want to sort the start array but then reorder the end array according to the sorted array, e.g.
    {1, 4, 3} is my start
    {2, 5, 7} is my end
    each coordinates correspond to each other.

    then I sort the start to be {1, 3, 4} and I want the end to look like {2, 7, 5}.
    I can of course call the std::sort function on start, but how do I reorder the end?
    First, why an int*? Why not just a vector<int>?

    1) Copy both arrays to a vector of std::pair<int,int>. The "first" would be the elements in "start", the second are the elements in "end". So here is what you have:
    Code:
    <1, 2>  first pair
    <4, 5> second pair
    <3, 7> third pair.
    So you have a vector of 3 pairs.

    2) Call std::sort to sort the first of the pair. By sorting on the first, you are automatically bringing the second for the ride. So at the end the vector of pairs will look like this:
    Code:
    <1, 2>  first pair
    <3, 7>  second pair.
    <4, 5>  third pair
    3) Now go through the vector and copy the items back to your original structures.

    Here is an example of initially setting this up.

    Code:
    #include <vector>
    #include <map>
    
    std::vector<std::pair<int, int> > TempVect;
    std::vector<int> Item1;
    std::vector<int> Item2;
    //...
    using namespace std;
    
    int main()
    {
       Item1.push_back(1);
       Item1.push_back(4);
       Item1.push_back(3);
    
       Item2.push_back(2);
       Item2.push_back(5);
       Item2.push_back(7);
    
       for (int i = 0; i < 3; ++i)
           TempVect.push_back(make_pair(Item1[i], Item2[i]));
    
    }
    I left out the call to std::sort, since this looks like homework. But this gives you an idea of what I'm referring to.

    There are probably better ways, but this is usually how you sort data that is "disjoint" -- you copy the data to a single, easily sortable data structure, then you sort the structure, and at the end, you copy the structure back to your original data area.

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Jan 2009
    Posts
    596

    Re: sorting algorithm

    The other way to do this, without needing to create extra tempory copies of the arrays, is to rewrite a standard sort algorithm so it takes in two arrays rather than just one. Then, within the algorithm, every time you move items in the first array (based upon the values in the first array), you move the corresponding items in the second array also.

    So, to clarify, if you are doing a bubblesort for example, and you find that firstArray[5] > firstArray[6], you would not only swap firstArray[5] with firstArray[6], but would also swap secondArray[5] with secondArray[6].

  4. #4
    Join Date
    Apr 1999
    Posts
    27,449

    Re: sorting algorithm

    Quote Originally Posted by Peter_B View Post
    The other way to do this, without needing to create extra tempory copies of the arrays, is to rewrite a standard sort algorithm
    I would rather create copies and call std::sort then try to reinvent the wheel. You're greatly increasing the chances of introducing bugs, as well as taking time making sure the home-made sort actually works correctly. In addition, the OP stated they wanted to use std::sort() but didn't know how to set it up to "parellel sort" two disparate arrays.

    The code I posted needs just 5 more lines of code to accomplish the OP's task -- one line to call std::sort() , a couple more lines of executable code to write the sort predicate function, and a couple more lines to copy the data back to the arrays. Very simple, if the OP reads the docs on std::sort and predicate functions -- once that's done, the code just magically works without writing any sorting code. I would have completed the OP's assignment, but wanted to leave these 4 of 5 lines of code out due to the OP's post having homework assignment written all over it.
    So, to clarify, if you are doing a bubblesort for example,
    If the OP is doing a bubble sort, and there are many items in his array, creating temporaries and calling std::sort will be on average, an order of magnitude faster in terms of speed.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 25th, 2011 at 03:01 PM.

  5. #5
    Join Date
    Jan 2009
    Posts
    596

    Re: sorting algorithm

    Yes, I agree that making pairs and using std:sort() is much quicker to implement, and easier to guarantee to be bug-free. I was merely giving an alternative way to solve the original problem which has a different trade-off between coding ease and memory use. It is always useful to know different ways of doing things - which method you use in any particular case being determined by the constraints of that case.

    You're greatly increasing the chances of introducing bugs, as well as taking time making sure the home-made sort actually works correctly.
    If you already have a working, bug-free sort algorithm, modifying it to do the parallel sort shouldn't be a problem - though obviously you have to be careful. If you don't already have the bug-free sort then yes, it will take lots more time to get working.

    As for bubblesort, I definitely do not recommend using it! It was just the first algorithm to come to mind (my mind works alphabetically )

  6. #6
    Join Date
    Nov 2011
    Posts
    2

    Re: sorting algorithm

    Hi Guys, how can you call sort on vector<pair<> >? Does it automatically know it only sorts the first coordinate?
    Thx.

  7. #7
    Join Date
    Jan 2009
    Posts
    596

    Re: sorting algorithm

    Quote Originally Posted by happybo7 View Post
    Hi Guys, how can you call sort on vector<pair<> >? Does it automatically know it only sorts the first coordinate?
    Thx.
    The default comparison operators, defined in <utility>, will compare by the first elements, then by the second. So although technically it doesn't just sort by the first coordinate you will get what you want from this.

    If you want other behaviour you just use the version of std::sort which takes a comparison function.

  8. #8
    Join Date
    Apr 1999
    Posts
    27,449

    Re: sorting algorithm

    Quote Originally Posted by happybo7 View Post
    Hi Guys, how can you call sort on vector<pair<> >? Does it automatically know it only sorts the first coordinate?
    Thx.
    The std::sort function has a version that has 3 arguments. That is the one you want to use.

    In my post to Peter B, I mentioned that you need to write the comparison function not the sorting function. It is the comparison function that is missing, and that is merely a one line function.

    http://www.cplusplus.com/reference/algorithm/sort/

    Look at the second prototype for std::sort, and the example in the link above. The comparison function takes two arguments and returns a bool. The two arguments are the types you're storing in the vector, in your case, the type is pair<int,int>.

    So in your compare function, you will get two pair<int,int> arguments, and you return true if the first pair comes before the second pair, false otherwise.

    Basically, the std::sort function you are to use repeatedly calls your comparison function with two values, and you just return back to the sorter which one of the two values comes before the other.

    Regards,

    Paul McKenzie

  9. #9
    Join Date
    Jan 2009
    Posts
    596

    Re: sorting algorithm

    Quote Originally Posted by Paul McKenzie View Post
    The std::sort function has a version that has 3 arguments. That is the one you want to use.
    In this case, the 2 argument version will work fine. That will use operator< for the pair, which unless you redefine it will sort firstly by the first element then by the second. This will give the correct behaviour for the problem as stated by the OP. And writing less code is better

    http://www.cplusplus.com/reference/std/utility/pair/

  10. #10
    Join Date
    Apr 1999
    Posts
    27,449

    Re: sorting algorithm

    Quote Originally Posted by Peter_B View Post
    In this case, the 2 argument version will work fine. That will use operator< for the pair, which unless you redefine it will sort firstly by the first element then by the second. This will give the correct behaviour for the problem as stated by the OP. And writing less code is better

    http://www.cplusplus.com/reference/std/utility/pair/
    Yes, since the OP is only concerned with the first's of the pair, then the operator < will work just fine and he needs only the two argument version of std::sort. Thanks.

    Regards,

    Paul McKenzie

  11. #11
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,721

    Re: sorting algorithm

    You might also consider replacing the two arrays with one array of a user-defined class:

    Code:
    struct Interval
    {
      int start;
      int end;
      
      Interval(int start_in = 0 , int end_in = 0) : start(start_in) , end(end_in) {}
      
      bool operator < (const Interval & rhs) const
      {
        return start < rhs.start;
      }
      
    };

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured