<algorithm> sort custom condition

Question

Okay, so I've tried to use sort to vector of items so the size of two adjecant items is <= 2d. So here's my attempt:

struct item{
    long number;
    long size;
};

// d is global variable.
bool check(const item& x, const item& y)
{
    return ((x.size + y.size) <= (2 * d));
}

// Items is a vector of item.
sort(items.begin(), items.end(), check); 

What am I doing wrong or it's even impossible to sort using condition like that ?

Answer 1

it's even impossible to sort using condition like that ?

No. The comparer in sort must satisfy the criteria of a strict weak ordering which yours clearly doesn’t (for instance it’s not irreflexive).

Answer 2

You're using the sort() method wrong.

STL sort is used to order a list of elements. For an 'ordering', you need to satisfy conditions like:

1. if check( A, B ) == false AND A != B, then check( B, A ) returns true.
2. if check( A, B ) == false AND check( B, C) == false AND A, B, C are distinct, then check ( A, C ) returns false.

A good idea for where you can use STL's sort() is, given your list of items S and the order you want the items to be in:

1. If the order of the items in S changes, the output order should remain the same.
2. The output is unique.
3. All the items in the output order have some relation that is a strict partial order relation.

If this is the case, then you probably can write the check function to work for you :)

Answer 3

This problem cannot be solved in O(N log N) time. I don't know if it's NP-hard, but it's quite non-trivial. I do think it's safe to say that a program solving the problem as expressed in your code would require exponential time. There are such programs: I think it could be fiddled around and plugged into a linear optimizer.

No standard library function will get you even most of the way to a general solution. There are no standard library functions slower than O(N log N), and none solve problems that may be intractable.

This problem is intractable if, for example, every size equals 10 * d.