3 ms·

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.

by wffurr 3y ago

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.

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.

by 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.