Why can't parity spoil a C # List <T> list?

Question

This is a somewhat obscure question, but after spending an hour tracking the error, I, although it’s worth asking ...

I wrote a custom order for a struct and made one mistake:

• My structure has a special state, let's call it "min".
• If the structure is in the min state, then it is smaller than any other structure.
• My CompareTo method made one mistake: a.CompareTo(b) returned -1 when a was "min", but, of course, if b also "min", it should return 0.

Now this error completely ruined the List<MyStruct> Sort() method: the entire list (sometimes) would go out in random order.

• My list contains only one object in the "min" state.
• It seems that my mistake can only affect things if one "min" object was mapped to itself.
• Why does this happen even when sorting?
• And even if this happened, how could this lead to the wrong order of two non-min objects?

Using the LINQ OrderBy method can cause an infinite loop ...

A small, complete, test example:

 struct MyStruct : IComparable<MyStruct> { public int State; public MyStruct(int s) { State = s; } public int CompareTo(MyStruct rhs) { // 10 is the "min" state. Otherwise order as usual if (State == 10) { return -1; } // Incorrect /*if (State == 10) // Correct version { if (rhs.State == 10) { return 0; } return -1; }*/ if (rhs.State == 10) { return 1; } return this.State - rhs.State; } public override string ToString() { return String.Format("MyStruct({0})", State); } } class Program { static int Main() { var list = new List<MyStruct>(); var rnd = new Random(); for (int i = 0; i < 20; ++i) { int x = rnd.Next(15); if (x >= 10) { ++x; } list.Add(new MyStruct(x)); } list.Add(new MyStruct(10)); list.Sort(); // Never returns... //list = list.OrderBy(item => item).ToList(); Console.WriteLine("list:"); foreach (var x in list) { Console.WriteLine(x); } for (int i = 1; i < list.Count(); ++i) { Console.Write("{0} ", list[i].CompareTo(list[i - 1])); } return 0; } } 

Answer 1

It seems that my mistake can only affect things if one "min" object was mapped to itself.

Not really. It could also be called if there were two different "minimal" objects. If you sort the list at a specific time, this can happen only if the item is compared with itself. But another case deserves consideration as a whole from the point of view of why the provision of non-transitive comparison with a method awaiting transient comparison is very bad.

Why does this happen even when sorting?

Why not?

List<T>.Sort() works with Array.Sort<T> on its elements. Array.Sort<T> in turn, uses a mixture of Insertion Sort, Heapsort, and Quicksort, but for simplicity, consider the general quicksort. For simplicity, we will use IComparable<T> directly, and not through System.Collections.Generic.Comparer<T>.Default :

 public static void Quicksort<T>(IList<T> list) where T : IComparable<T> { Quicksort<T>(list, 0, list.Count - 1); } public static void Quicksort<T>(IList<T> list, int left, int right) where T : IComparable<T> { int i = left; int j = right; T pivot = list[(left + right) / 2]; while(i <= j) { while(list[i].CompareTo(pivot) < 0) i++; while(list[j].CompareTo(pivot) > 0) j--; if(i <= j) { T tmp = list[i]; list[i] = list[j]; list[j] = tmp; i++; j--; } } if(left < j) Quicksort(list, left, j); if(i < right) Quicksort(list, i, right); } 

This works as follows:

• Select an element called a bar from the list (we use the middle).
• Change the order of the list so that all elements with values ​​smaller than the pivot point come before the pivot point, while all elements with values ​​greater than the pivot point come after it.
• Now the rod is in its last position with an unsorted sub-list before and after it. Recursively apply the same steps to these two sub-lists.

Now there are two things that you should pay attention to the above code example.

Firstly, we do not prevent pivot from comparing itself. We could do it, but why should we? First, for this we need some kind of comparison code that you have already provided in your CompareTo() method. To avoid wasted CompareTo , we would either have to call CompareTo() * the extra time for each comparison (!), Or track the position of the pivot , which would add more waste than was removed.

And even if this happened, how could this lead to an incorrect relative order of the two non-mines?

Since the sections are quicksort, it does not make a massive view, but rather is a series of mini-roles. Therefore, an incorrect comparison gives a number of opportunities to spoil parts of these genera, each time leading to a sub-list of incorrectly sorted values, which the algorithm considers "considered". Thus, in cases where an error occurs in the companion, its damage can spread over most of the list. Just like he does his sorting by a series of mini-sorts, so that he will do fuzzy sortings by a series of mini-sorting buggies.

Using the LINQ OrderBy Method May Cause an Infinite Loop

It uses the Quicksort option, which guarantees stability; the two equivalent elements will still have the same relative order after the search as before. Complex complexity, apparently, leads to the fact that he not only compares the element with himself, but continues to do this forever, as he tries to make sure that he is both in front of himself and in the same order as he was before . (Yes, the last sentence does not make sense, and that is why it never returns).

* If it was a reference type, not a value type, we could quickly make ReferenceEquals , but besides the fact that this would not be good with structures, and the fact that if it really was an economical time for the type in question , it should have if(ReferenceEquals(this, other)) return 0; in CompareTo in any case, it still will not fix the error after more than "minimal" elements appear in the list.