Im trying to do a merge sort in cpp on a vector called x, which contains x coordinates. As the mergesort sorts the x coordinates, its supposed to move the corresponding elements in a vector called y, containing the y coordinates. the only problem is that i dont know how to (or if i can) return both resulting vectors from the merge function. alternatively if its easier to implement i could use a slower sort method.
+1
A:
Try something like this:
struct Point {
int x;
int y;
operator <(const Point &rhs) {return x < rhs.x;}
};
vector<Point> my_points.
mergesort(my_points);
Or if you want to sort Points with equal x value by the y cordinate:
Also, I thought I'd add, if you really ever need to, you can alway return a std::pair. A better choice is usually to return through the function parameters.
operator <(const Point &rhs) {return (x < rhs.x || x == rhs.x && y < rhs.y);}
JoshD
2010-10-07 08:05:47
Ironic - a vector of vectors...
Preet Sangha
2010-10-07 08:10:09
@Preet Sangha: :) Yes indeed.
JoshD
2010-10-07 08:15:06
Thank you. The problem is the way I obtain the coordinates and the best way for my application is to seperate them. is possible to have a struct with the two vectors, sorted by y coordinates, then have the merge function create a new struct that has the new vectors, sorted by x? or have the function change an existing struct.
2010-10-07 08:28:35
+1
A:
No, you cannot return 2 results from a method like in this example.
vector<int>, vector<int> merge_sort();
What you can do is pass 2 vectors by reference to a function and the resultant mergesorted vector affects the 2 vectors...e.g
void merge_sort(vector<int>& x, vector<int>& y);
Ultimately, you can do what @JoshD mentioned and create a struct called point and merge sort the vector of the point struct instead.
The Elite Gentleman
2010-10-07 08:10:00
A:
Returning vectors is most probably not what you want, as they are copied for this purpose (which is slow). Have a look at this implementation, for example.
hannes
2010-10-07 08:17:58