CODEWITHSUNDEEP
c++arrayssortingvector
DARKMATTER
DARKMATTER

Reputation: 373

Sort multi-dimensional vector in c++ lexicographically

Assuming I have this 2-dimensional vector arr which is 5X3:

3, 4, 1
1, 7, 2
5, 2, 8
1, 3, 1
5, 0, 0

and I want to sort it lexicographically, like so:

1, 3, 1
1, 7, 2
3, 4, 1
5, 0, 0
5, 2, 8

in other words, I want the rows be sorted primarily according to the first elements, and then if two rows have equal first elements, the rows be sorted according to the second elements, I don't want any sorting relative to the third elements.

Here is the code that I wrote:

bool compare (vector<float> ar1, vector<float> ar2) {

if (ar1[0]<ar2[0]) return 1;
if (ar1[0]>ar2[0]) return 0;
if (ar1[1]<ar2[1]) return 1;
if (ar1[1]>ar2[1]) return 0;
return 0;
}

stable_sort(arr.begin(), arr.end(), compare);

the code seems to give the desired results for the above vector. However, in an actual project where I have a 4506X3 vector of floats it doesn't sort the second column! Can the big size of this vector be a problem? In that case, what is the solution? Should I sort the first column, then divide the array based on rows with the same first elements, sort the second columns of the smaller arrays and then merge them? Is there a better solution?

I appreciate any suggestions.

Upvotes: 2

Views: 1477

Answers (2)

DARKMATTER
DARKMATTER

Reputation: 373

I found the problem; I had these rows:

-19.235676 44.020599 0.151365
-19.235676 43.333611 0.201697
-19.235674 40.585663 0.151365

which when I read them from file and pushed them back to my vector, they turned into:

-19.2357 44.0206 0.151365 
-19.2357 43.3336 0.201697 
-19.2357 40.5857 0.151365

so, I was expecting that the third row comes before the first and the second one.

Upvotes: 1

juanchopanza
juanchopanza

Reputation: 227618

You don't need your own comparator. The default will work out of the box because there is already an operator< for std::vector which performs a lexicographical comparison.

std::stable_sort(arr.begin(), arr.end());

Upvotes: 4

Related Questions