Ordering coordinates c-CodePudding

I'm trying to order a list of coordinates in c , but it's not working. i'm using c sort function, and first ordering the x values and then the y values

if n = 9 and the coordinates:

(2,2) (2,3) (1,2) (1,3) (2,1) (1,1) (3,2) (3,3) (3,1)

the output should be:

(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3 ,3)

But for some reason, it is:

(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
(3,2)
(3,3)
(3,1)

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct{
    short x;
    short y;
} coord;

bool comparex( coord a, coord b){
    if(a.x < b.x)
        return 1;
    else return 0;
}

bool comparey(coord a, coord b){
    
    if(a.x == b.x && a.y < b.y){
        return 1;
    } else return 0;
}


int main(){
    
    
    short n;
    coord v[1001];
    
    while(cin >> n){
        for (int i=1; i<=n; i  ){
            cin >> v[i].x;
            cin >> v[i].y;
        }
        
        sort(v 1, v n, comparex);
        sort(v 1, v n, comparey);
        for (int i=1; i<=n; i  ){
            cout << v[i].x << ' ' << v[i].y << endl;
        }
                    
    }

    
    return 0;
}

CodePudding user response：

std::sort isn't stable, use stable_sort or better just use a comparator that compares both elements at once:

sort(v 1, v n, [](coord a, coord b)
{
  return std::tie(a.x, a.y) < std::tie(b.x, b.y));
});

This uses std::tie which creates a std::tuple which automatically has the expected behaviour when comparing a pair of elements.

Note that for stable_sort to work you need to change comparey to just compare y (as its name suggests it does):

bool comparey(coord a, coord b){
    return a.y < b.y;
}

Your current implementation doesn't provide a strict weak ordering so can't be used as a comparator for either sort or stable_sort.

CodePudding user response：

Your comparison is flawed:

bool comparey(coord a, coord b){
    
    if(a.x == b.x && a.y < b.y){
        return 1;
    } else return 0;
}

You always return 0 (should be false) when a.x != b.x. For example comparey({0,1}, {1,1}) == false but also comparey({1,1},{0,1}) == false.

You can use std::pair for the comparison:

bool comparey(coord a, coord b){
    return std::pair(a.x,a.y) < std::pair(b.x,b.y);
}

or use std::tie to avoid constructing the pairs:

bool comparey(coord a, coord b){
    return std::tie(a.x,a.y) < std::tie(b.x,b.y);
}

CodePudding user response：

This code invokes undefined behavior because your comparey does not satisfy the requirements of a Compare function. Specifically, the relation induced by defining equiv(a, b) to mean !comparey(a, b) && !comparey(b, a) is not transitive and therefore is not an equivalence relation.

Let a be {1, 0}.

Let b be {2, 0}.

Let c be {1, 1}.

Because 1 != 2, the following are all false: comparey(a, b), comparey(b, a), comparey(b, c) and comparey(c, b).

Therefore, equiv(a, b) and equiv(b, c) are both true. It should be the case that equiv(a, c) is true as well.

However, comparey(a, c) is true, not false. Therefore equiv(a, c) is false, when it should be true.

Therefore attempting to use comparey as a comparator for sort invokes undefined behavior.

Possible fixes:

Use a single comparison function that performs lexicographic comparison of elements.

#include <tuple>

bool compare(coord a, coord b){
    return std::tie(a.x, a.y) < std::tie(b.x, b.y);
}

Make it so that comparey only compares the y coordinate, and use stable_sort so that applying comparey won't reorder elements that have the same y coordinate but different x coordinates.

bool comparey(coord a, coordb){
    return a.y < b.y;
}

// In calling code:
#include <algorithm>

std::stable_sort(v 1, v n, comparey);