Is it safe to sort a container which may contain infinities using quicksort?

Question

I have realized that in order for quicksort to work, all the infinities need to be equal.

In other words, such a criterium 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 criterium. The unequalness depends on the order in which the entities enter the operator. I found out, that such a ordering fails.

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 of

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

methods, I would like to use just

   float Entity::value() const;

And have it return

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

in cases where

bool Entity::valueIsInfinite() const;

would return true.

Now I tested this approach and it seems to work. But I am concerned about other ways in which an infinity may arise. For example:

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

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

Answer 1

Without the presence of NaNs, infinities are fine with the regular operator <:

• +∞ < +∞ is false: < is irreflexive;
• if +∞ < x is true then x < +∞ is false for non-infinity values: < is antisymmetric;
• if +∞ < x is true and x < y is true, then +∞ < y is true: < is transitive;
• if +∞ is incomparable (not less, not greater) with x, and x is incomparable with y, then +∞ is incomparable with y: < displays transivity of equivalence.

(similar properties are valid for -∞)

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

However, with NaNs, the antisymmetry property is broken: NaN < 1 is false, and 1 < NaN is false too. You can solve this by ordering all NaNs either before or after all non-NaNs, in a manner similar to 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 on the C++11 standard library, or implemented quite easily as return x != x;)

With this, we get NaN < 1 as true, and 1 < NaN as false, while the other properties still hold.