-
November 24th, 2011, 09:42 PM
#1
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?
-
November 24th, 2011, 10:51 PM
#2
Re: sorting algorithm
Originally Posted by happybo7
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
-
November 25th, 2011, 07:19 AM
#3
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].
-
November 25th, 2011, 02:58 PM
#4
Re: sorting algorithm
Originally Posted by Peter_B
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.
-
November 25th, 2011, 03:40 PM
#5
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 )
-
November 25th, 2011, 04:57 PM
#6
Re: sorting algorithm
Hi Guys, how can you call sort on vector<pair<> >? Does it automatically know it only sorts the first coordinate?
Thx.
-
November 25th, 2011, 06:08 PM
#7
Re: sorting algorithm
Originally Posted by happybo7
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.
-
November 25th, 2011, 10:40 PM
#8
Re: sorting algorithm
Originally Posted by happybo7
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
-
November 26th, 2011, 07:29 AM
#9
Re: sorting algorithm
Originally Posted by Paul McKenzie
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/
-
November 26th, 2011, 10:51 AM
#10
Re: sorting algorithm
Originally Posted by Peter_B
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
-
November 28th, 2011, 08:06 AM
#11
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|