Is it safe to sort a container that can contain infinity with quicksort?

Question

I realized that for quicksort to work, all infinities must be equal.

In other words, such a criterion is not enough:

class Entity { public: float value() const; bool valueIsInfinite() const; }; class Criterium { bool operator()(Entity left, Entity right)const { if (left.valueIsInfinite()) return false; return left.value() < right.value(); } } const Criterium criterium; QVector<Entity> container; qSort<container.begin(), container .end(), criterium> 

This sorting fails because not all infinities are equal according to the criterion. The imbalance depends on the order in which the subjects enter the operator. I found out that this order does not work.

I need something like this:

 class Criterium { bool operator()(Entity left, Entity right)const { if (left.valueIsInfinite() && right.valueIsInfinite()) return false; if (left.valueIsInfinite() && !right.valueIsInfinite()) return false; if (!left.valueIsInfinite() && right.valueIsInfinite()) return true; return left.value() < right.value(); } } 

But suppose that instead

  float Entity::value() const; bool Entity::valueIsInfinite() const; 

I would like to use only

  float Entity::value() const; 

And bring him back

 std::numeric_limits<float>::infinity(); 

in cases where

 bool Entity::valueIsInfinite() const; 

will return true.

Now I have tested this approach and it seems to have worked. But I am worried about other ways in which infinity may arise. For instance:

 float otherInfinity = exp(std::numeric_limits<float>::infinity()); 

This infinity seems to be the same. But I want to be sure. I know that the C ++ standard does not mention the details of a floating point arithmetic implementation, but if I use gcc, is it safe in all cases? I mean, all infinities created equal in gcc? Is it safe to sort a container with floats that can contain infinities that have arisen at different times?

Answer 1

Without the presence of NaN, infinities are exact with the regular operator < :

• + ∞ <+ ∞ is false: < is non-reflexive;
• if + ∞ <x is true, then x <+ ∞ is not true for values ​​without infinity: < is antisymmetric;
• if + ∞ <x is true and x <y is true, then + ∞ <y is true: < is transitive;
• if + ∞ is incomparable (no less, no more) with x, and x is not comparable with y, then + ∞ is not comparable with y: < displays the transitivity of equivalence.

(similar properties apply to -∞)

Given those operator< properties on floats without NaNs, this is a strict weak ordering and, therefore, is suitable for standard library style ordering operations.

However, with NaNs, the antisymmetry property is broken: NaN <1 is false, and 1 <NaN is also false. You can solve this by ordering all NaNs either before or after all non-NaNs, in the same way as your proposed strategy:

 struct Criterion { bool operator()(Entity left, Entity right)const { // NaNs come before non-NaNs if (isnan(left.value()) && isnan(right.value())) return false; if (!isnan(left.value()) && isnan(right.value())) return false; if (isnan(left.value()) && !isnan(right.value())) return true; return left.value() < right.value(); } } 

( isnan can be found in the C ++ 11 standard library or easily implemented as return x != x; )

With this, we get NaN <1 as true, and 1 <NaN as false, while the rest of the properties are preserved.

Answer 2

If you use this:

 bool operator()(Entity left, Entity right)const { return !(left.valueIsInfinite() && right.valueIsInfinite()) && left.value() < right.value(); } 

Then infinities are considered one order, since no one comes before another ...