Sorting an array of paired numbers with NaN in it

Question

This is more like the question “Can you explain this” than anything else.

I ran into a problem at work, where we used the NaN values ​​in the table, but when the table was sorted, it turned out in a very strange, strange way. I thought that NaN was interfering with something, so I wrote a test application to find out if this is true. This is what I did.

static void Main(string[] args) { double[] someArray = { 4.0, 2.0, double.NaN, 1.0, 5.0, 3.0, double.NaN, 10.0, 9.0, 8.0 }; foreach (double db in someArray) { Console.WriteLine(db); } Array.Sort(someArray); Console.WriteLine("\n\n"); foreach (double db in someArray) { Console.WriteLine(db); } Console.ReadLine(); } 

What gave the result:

Before:

 4,2,NaN,1,5,3,NaN,10,9,8 

After:

 1,4,NaN,2,3,5,8,9,10,NaN 

So yes, NaN somehow made the sorted array sorted in a weird way.

To quote Fry; "Why is this?"

Answer 1

Edit (end. End.): This is a mistake.

See error report Error in list <double / single> .Sort () [.NET35] in the list that contains double.NaN and go, give Hans Passan a vote on Why .NET 4.0 sorts this array differently than. NET 3.5? from which I broke the link.

Historical reflections

[Cm. message: Why does .NET 4.0 sort this array differently than .NET 3.5? where, hopefully, a more useful discussion of this particular problem can be thought up for real. I also posted this answer here.]

The behavior specified in .NET4 from Phil is specified in CompareTo. See double.CompareTo for .NET4. This is the same behavior as in .NET35, but should be consistent in both versions, according to the method documentation ...

Array.Sort(double[]) : doesn't seem to use CompareTo(double[]) as expected, and this can be a very mistake - note the difference in Array.Sort (object []) and Array.Sort (double [ ]) below. I would like to clarify / fix the following:

In any case, answers using > and < and == explain why these statements do not work, but cannot explain why Array.Sort leads to unexpected output. Here are some of my finds that are as scarce as they can be.

First, double.CompareTo(T) documentation - this ordering is clearly defined in accordance with the documentation

Less than zero: This instance is less than the value. -or- This instance is not a number (NaN), but the value is a number.

Zero This instance is equal to the value. -or- And this instance and value are not a number (NaN), PositiveInfinity or NegativeInfinity.

Greater than zero: This instance is greater than the value. -or- This instance is a number and a value, not a number (NaN).

In LINQPad (3.5 and 4 both have the same results):

 0d.CompareTo(0d).Dump(); // 0 double.NaN.CompareTo(0d).Dump(); // -1 double.NaN.CompareTo(double.NaN).Dump(); // 0 0d.CompareTo(double.NaN).Dump(); // 1 

Using CompareTo(object) has the same results:

 0d.CompareTo((object)0d).Dump(); // 0 double.NaN.CompareTo((object)0d).Dump(); // -1 double.NaN.CompareTo((object)double.NaN).Dump(); // 0 0d.CompareTo((object)double.NaN).Dump(); // 1 

So no problem.

Now from Array.Sort(object[]) documentation is not used > , < or == (according to the documentation) is just CompareTo(object) .

Sorts the elements in the entire one-dimensional array using the IComparable implementation of each element of the array.

Similarly, Array.Sort(T[]) uses CompareTo(T) .

Sorts the elements in the entire array using the implementation of the universal IComparable (Of T) interface of each element of the array.

We'll see:

LINQPad (4):

 var ar = new double[] {double.NaN, 0, 1, double.NaN}; Array.Sort(ar); ar.Dump(); // NaN, NaN, 0, 1 

LINQPad (3.5):

 var ar = new double[] {double.NaN, 0, 1, double.NaN}; Array.Sort(ar); ar.Dump(); // NaN, 0, NaN, 1 

LINQPad (3.5) - NOTE. MASS OF THE OBJECT , and the behavior is "expected" in the CompareTo contract.

 var ar = new object[] {double.NaN, 0d, 1d, double.NaN}; Array.Sort(ar); ar.Dump(); // NaN, NaN, 0, 1 

Hm. Indeed. Finally:

I have no IDEA.

Happy coding.

Answer 2

I believe that since

 a < NaN == false a > NaN == false a == NaN == false 

therefore, the comparison with them breaks down, and this casts away the whole view.

Answer 3

Conceptually, NaN is not a number, so comparison with a number does not make sense, therefore:

 a < NaN = false for all a, a > NaN = false for all a and NaN != NaN (!) 

To solve this problem, you need to write your own comparator that uses IsNaN to make NaNs less (or more) of all numbers so that they all appear at one end of the sort.

Edit: Here is a sample comparison version:

 class Program { private static int NaNComparison(double first, double second) { if (double.IsNaN(first)) { if (double.IsNaN(second)) // Throws an argument exception if we don't handle both being NaN return 0; else return -1; } if (double.IsNaN(second)) return 1; if (first == second) return 0; return first < second ? -1 : 1; } static void Main(string[] args) { var doubles = new[] { double.NaN, 2.0, 3.0, 1.0, double.NaN }; Array.Sort(doubles, NaNComparison); } } 

Answer 4

Actually, the weird sorting behavior is the result of a bug in .NET 3.5. The error was resolved using .NET 4.0.

The only way to resolve this is to use your own custom mapper or upgrade to .NET 4.0. See Why does .NET 4.0 sort this array differently than .NET 3.5?

Answer 5

since you are using the default sort, which is a QuickSort algorithm; the implementation is unstable; that is, if two elements are equal, their order cannot be saved.