4 ms·

"Unspecified order" seems a poor guarantee. I think a sort implementation should return elements in an order consistent with a subset of the comparison calls i

by devit 3y ago

"Unspecified order" seems a poor guarantee. I think a sort implementation should return elements in an order consistent with a subset of the comparison calls it makes, and that subset should be such that it fully determines the order. An even better guarantee is that the subset should be the whole set of comparison calls.

deleted 3y ago
[deleted]
wffurr 3y ago
Is there any existing sort implementation that does this? The closest I can think of is stable sorts which aren’t quite what you described.
- Someone 3y ago
  > I think a sort implementation should return elements in an order consistent with a subset of the comparison calls it makes, and that subset should be such that it fully determines the order. > An even better guarantee is that the subset should be the whole set of comparison calls. For consistent comparator functions, all decent implementations “return elements in an order consistent with a subset of the comparison calls it makes, and that subset should be such that it fully determines the order”, because that’s the definition of sorting. They also have the added feature that that subset is the full set of the comparison calls they make. Why would they make more calls than necessary? For buggy comparator functions, once you hit even a single inconsistency it can’t be the whole set of comparison calls. Also, for a buggy comparator function, you can’t count on the comparator function to be antisymmetric, so it may both say that a < b and b < a, and you can’t even count on it returning the same value when called twice with the same arguments (a comparator could return a coin flip, for example) However, if you’re willing to make all the n × (n - 1) comparison calls, it seems reasonable to me that you can find a subset that defines an ordering. I can only think of an heuristic argument for that, though, not of a proof. That argument is that there are n! possible orderings you can return, and each has a ‘chance’ of 1/2^(n-1) of only containing links that are consistent with the comparator function, and the former is way larger than the latter. Given that chances are at least one would be consistent, and define the order. However, I don’t see what good that would do. If your code can detect that the comparator function is buggy, it’s better to signal that than to spend time finding some semi-random ordering that partially satisfies the comparator function.
tedunangst 3y ago
Who's going to write the specification for how a sort algorithm behaves when the comparator lies?
Guvante 3y ago
This isn't just <= vs <. It is absolutely possible to write a comparator that evaluates things in a circle e.g. 1<2 && 2<3 && 3<1. At that point it is impossible to "do your best" there is no correct answers only wrong ones. (You have to violate a comparison here)
- devit 3y ago
  The sort function has no reason to ask for all three comparisons. Rather, it can ask for two comparisons and act according to the results (e.g. it learns that 1 < 2 and 2 < 3 and returns [1, 2, 3]). This makes the output unspecified in general, but it will be consistent with the information received and the calls made even if the comparator doesn't form an ordering, which is what one would expect.

by devit 3y ago

deleted 3y ago

[deleted]

wffurr 3y ago

Is there any existing sort implementation that does this? The closest I can think of is stable sorts which aren’t quite what you described.

Someone 3y ago
> I think a sort implementation should return elements in an order consistent with a subset of the comparison calls it makes, and that subset should be such that it fully determines the order. > An even better guarantee is that the subset should be the whole set of comparison calls. For consistent comparator functions, all decent implementations “return elements in an order consistent with a subset of the comparison calls it makes, and that subset should be such that it fully determines the order”, because that’s the definition of sorting. They also have the added feature that that subset is the full set of the comparison calls they make. Why would they make more calls than necessary? For buggy comparator functions, once you hit even a single inconsistency it can’t be the whole set of comparison calls. Also, for a buggy comparator function, you can’t count on the comparator function to be antisymmetric, so it may both say that a < b and b < a, and you can’t even count on it returning the same value when called twice with the same arguments (a comparator could return a coin flip, for example) However, if you’re willing to make all the n × (n - 1) comparison calls, it seems reasonable to me that you can find a subset that defines an ordering. I can only think of an heuristic argument for that, though, not of a proof. That argument is that there are n! possible orderings you can return, and each has a ‘chance’ of 1/2^(n-1) of only containing links that are consistent with the comparator function, and the former is way larger than the latter. Given that chances are at least one would be consistent, and define the order. However, I don’t see what good that would do. If your code can detect that the comparator function is buggy, it’s better to signal that than to spend time finding some semi-random ordering that partially satisfies the comparator function.

tedunangst 3y ago

Who's going to write the specification for how a sort algorithm behaves when the comparator lies?

Guvante 3y ago

This isn't just <= vs <. It is absolutely possible to write a comparator that evaluates things in a circle e.g. 1<2 && 2<3 && 3<1. At that point it is impossible to "do your best" there is no correct answers only wrong ones. (You have to violate a comparison here)

devit 3y ago
The sort function has no reason to ask for all three comparisons. Rather, it can ask for two comparisons and act according to the results (e.g. it learns that 1 < 2 and 2 < 3 and returns [1, 2, 3]). This makes the output unspecified in general, but it will be consistent with the information received and the calls made even if the comparator doesn't form an ordering, which is what one would expect.