Warum versäumt es die Gleichheit zu erkennen? C # ListT sort?

  

Es scheint, dass mein Fehler nur Auswirkungen auf die Dinge hätte, wenn das eine "min" Objekt mit sich selbst verglichen würde.

Nicht ganz. Es könnte auch sein, wenn zwei verschiedene "min" -Objekte vorhanden wären. Im Falle der Liste sortiert diese bestimmte Zeit, kann es nur passieren, wenn der Gegenstand mit sich selbst verglichen wird. Aber der andere Fall ist es wert, allgemein betrachtet zu werden, warum die Lieferung eines nicht-transitiven Vergleichs an eine Methode, die einen transitiven Vergleich erwartet, eine sehr schlechte Sache ist.

  

Warum würde das sogar beim Sortieren passieren?

Warum nicht?

List<T>.Sort() arbeitet mit dem Array.Sort<T> für seine Elemente. Array.Sort<T> verwendet wiederum eine Mischung aus Einfügesortierung, Heapsort und Quicksort, vereinfacht jedoch einen allgemeinen Quicksort. Der Einfachheit halber verwenden wir IComparable<T> direkt, anstatt via System.Collections.Generic.Comparer<T>.Default :

Dies funktioniert wie folgt:

1. Wählen Sie ein Element aus der Liste aus (wir verwenden die Mitte).
2. Ordnen Sie die Liste neu an, so dass alle Elemente mit Werten kleiner als der Pivot vor dem Pivot stehen, während alle Elemente mit Werten größer als der Pivot dahinter stehen.
3. Der Pivot befindet sich jetzt an seiner endgültigen Position mit einer unsortierten Unterliste davor und danach. Wenden Sie rekursiv die gleichen Schritte auf diese beiden Unterlisten an.

Nun sind zwei Dinge über den obigen Beispielcode zu beachten.

Erstens verhindern wir nicht, dass pivot mit sich selbst verglichen wird. Wir könnten das tun, aber warum sollten wir? Zum einen benötigen wir dafür einen Vergleichscode, den Sie bereits in Ihrer CompareTo() -Methode angegeben haben. Um den verschwendeten CompareTo zu vermeiden, müssten wir entweder CompareTo() * für jeden Vergleich (!) Eine zusätzliche Zeit nennen oder die Position von pivot verfolgen, was mehr Verschwendung hinzufügen würde als entfernt.

  

Und wenn ja, wie kann es dazu kommen, dass die relative Reihenfolge von zwei "Nicht-Min" -Objekten falsch ist?

Da es sich um Quicksort-Partitionen handelt, führt es keine massive Sortierung durch, sondern eine Reihe von Minisorten. Daher erhält ein falscher Vergleich eine Reihe von Möglichkeiten, Teile dieser Art zu vermasseln, wobei jedes Mal zu einer Unterliste von falsch sortierten Werten führt, die der Algorithmus als "behandelt" betrachtet. In den Fällen, in denen der Fehler im Vergleich auftritt, kann sein Schaden über einen großen Teil der Liste verteilt werden. Genauso wie es seine Art durch eine Reihe von Mini-Sortierungen erledigt, so wird es eine fehlerhafte Sortierung durch eine Reihe von fehlerhaften Mini-Sortierungen durchführen.

  

Die Verwendung der LINQ OrderBy-Methode kann eine Endlosschleife verursachen

Es verwendet eine Variante von Quicksort, die Stabilität garantiert; Zwei gleichwertige Elemente haben nach der Suche immer noch dieselbe relative Reihenfolge wie zuvor. Die zusätzliche Komplexität führt vermutlich dazu, dass das Objekt nicht nur mit sich selbst verglichen wird, sondern auch weiterhin für immer, da es versucht, sicherzustellen, dass es sowohl vor sich selbst als auch in der gleichen Reihenfolge ist wie es war Vor. (Ja, dieser letzte Satz macht keinen Sinn, und genau deshalb kehrt er nie zurück).

* Wenn dies ein Referenz- statt ein Werttyp wäre, könnten wir ReferenceEquals schnell machen, aber abgesehen davon, dass dies für Strukturen nicht gut ist, und die Tatsache, dass dies wirklich eine Zeitersparnis war für den fraglichen Typ sollte es trotzdem if(ReferenceEquals(this, other)) return 0; in CompareTo haben, es würde den Fehler immer noch nicht beheben, wenn mehr als ein "min" Elemente in der Liste waren.