3 ms·
They already mention the issue of using substraction for comparison; here's another different accidentally intransitive comparison function: int cmp(const
by skitter 3y ago
They already mention the issue of using substraction for comparison; here's another different accidentally intransitive comparison function:
int cmp(const float *a, const float *b) {
if (*a < *b) {
return 1;
} else if (*a == *b) {
return 0;
} else {
return -1;
}
}
- jstimpfle 3y agoIs it intransitive? Can you give a, b, c s.t. a < b and b < c, but not a < c?
- rrauenza 3y agoMaybe inf or nan? https://stackoverflow.com/a/42723797/2077386 https://stackoverflow.com/a/42723797/2077386
- scythe 3y agoTrivially, NaN != NaN, so this function is not even properly reflexive (i.e. for a = b = NaN we find cmp(&a,&b) = cmp(&b,&a) = 1).
- jstimpfle 3y agoI mean, yeah. It's not like there is a lot of meaning to NaN. For most applications, trying to sort NaNs is probably a bug in itself. So I think this is likely a perfectly valid comparison function. To make a point, here is a sorting function I'm using. static int cmp_seqnos(const void *a, const void *b) { uint64_t x = (const uint64_t *) a; uint64_t y = (const uint64_t *) b; if (y - x < ((uint64_t) 1 << 63)) return -1; return x != y; } I think this should work if there are uint64_t a, b: b - a < ((uint64_t) 1 << 63) and all values x from the set to be sorted are in the range a..b. Note that a < b isn't a requirement here. Sorting such numbers can be useful when dealing with sliding windows.
- ufo 3y agoMaybe theyre talking about NaN?Comparing against NaN return false. That doesn't violate transitivity, but it can confuse many sorting algorithms.
- rightbyte 3y agoNo, but you need a nan check in the above code. And a negative zero check if you are picky for sorting maybe.
- deleted 3y ago[deleted]