Warum enthält die Liste <T> .Sort-Methode gleiche IComparable <T> Elemente?

Question

Ich habe ein Problem damit, wie die List Sort-Methode das Sortieren behandelt. Gegeben das folgende Element:

class Element : IComparable<Element> 
{ 
    public int Priority { get; set; } 
    public string Description { get; set; } 

    public int CompareTo(Element other) 
    { 
     return Priority.CompareTo(other.Priority); 
    } 
} 

Wenn ich versuche, es auf diese Weise zu sortieren:

List<Element> elements = new List<Element>() 
          { 
           new Element() 
            { 
             Priority = 1, 
             Description = "First" 
            }, 
           new Element() 
            { 
             Priority = 1, 
             Description = "Second" 
            }, 
           new Element() 
            { 
             Priority = 2, 
             Description = "Third" 
            } 
          }; 
elements.Sort(); 

Dann wird das erste Element ist das zuvor zweite Element "Second". Oder, mit anderen Worten, diese Behauptung nicht:

Assert.AreEqual("First", elements[0].Description); 

Warum ist Neuordnungs .NET meine Liste, wenn die Elemente im Wesentlichen gleich sind? Ich möchte, dass es nur die Liste neu anordnet, wenn der Vergleich einen Wert ungleich null zurückgibt.

Answer 1

Aus der Dokumentation des List.Sort() -Methode von MSDN:

Diese Methode verwendet Array.Sort, die den QuickSort-Algorithmus verwendet. Diese Implementierung führt eine instabile Sortierung durch; Das heißt, wenn zwei Elemente gleich sind, wird ihre Reihenfolge möglicherweise nicht beibehalten. Im Gegensatz dazu behält eine stabile Sortierung die Reihenfolge der Elemente bei, die gleich sind.

Hier ist der Link: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Im Wesentlichen wird die Art, wie entworfen Durchführung und dokumentiert.

Answer 2

Sie sagten es, wie man Dinge vergleicht und es tat. Sie sollten sich nicht auf die interne Implementierung von Sort in Ihrer Anwendung verlassen. Deshalb können Sie CompareTo überschreiben. Wenn Sie einen sekundären Sortierparameter (in diesem Fall "Beschreibung") haben möchten, codieren Sie ihn in Ihr CompareTo. Sich darauf zu verlassen, wie Sort gerade funktioniert, ist eine großartige Möglichkeit, einen Fehler zu programmieren, der sehr schwer zu finden ist.

Sie könnten einen stabilen Quicksort für .NET finden oder verwenden Sie eine merge sort (die bereits stabil ist).

Answer 3

Sie können dies beheben, indem Sie Ihrer Struktur einen "Indexwert" hinzufügen und diesen in der CompareTo-Methode einschließen, wenn Priority.CompareTo 0 zurückgibt. Sie müssten dann den Wert "index" vor der Sortierung initialisieren.

Die CompareTo Methode würde wie folgt aussehen:

public int CompareTo(Element other) 
{ 
    var ret = Priority.CompareTo(other.Priority); 
    if (ret == 0) 
    { 
     ret = Comparer<int>.Default.Compare(Index, other.Index); 
    } 
    return ret; 
} 

Dann statt elements.Sort() zu tun, würden Sie tun:

for(int i = 0; i < elements.Count; ++i) 
{ 
    elements[i].Index = i; 
} 
elements.Sort(); 

Answer 4

die anderen Antworten Siehe warum List.Sort() ist instabil. Wenn Sie eine stabile Sortierung benötigen und .NET 3.5 verwenden, versuchen Sie Enumerable.OrderBy() (LINQ).

Answer 5

Wenn Sie wollten auf zwei Feldern statt einer sortieren Sie dies tun könnte:

class Element : IComparable<Element> 
{ 
    public int Priority { get; set; } 
    public string Description { get; set; } 

    public int CompareTo(Element other) 
    { 
     if (Priority.CompareTo(other.Priority) == 0) 
     { 
      return Description.CompareTo(other.Description); 
     } else { 
      return Priority.CompareTo(other.Priority); 
     } 
    } 
} 

Offensichtlich ist dies die Voraussetzung eines stabilen Suchalgorithmus nicht erfüllt; Es erfüllt jedoch Ihre Behauptung und ermöglicht die Kontrolle Ihrer Elementordnung im Falle der Gleichheit.Hier

Answer 6

ist eine Erweiterung Methode SortStable() für List<T> where T : IComparable<T>:

public static void SortStable<T>(this List<T> list) where T : IComparable<T> 
{ 
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList(); 
    list.Clear(); 
    list.AddRange(listStableOrdered); 
} 

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T> 
{ 
    public int Compare(T x, T y) 
    { 
     return x.CompareTo(y); 
    } 
} 

Test:

[Test] 
public void SortStable() 
{ 
    var list = new List<SortItem> 
        { 
         new SortItem{ SortOrder = 1, Name = "Name1"}, 
         new SortItem{ SortOrder = 2, Name = "Name2"}, 
         new SortItem{ SortOrder = 2, Name = "Name3"}, 
        }; 

    list.SortStable(); 

    Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1)); 
    Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1")); 
    Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2)); 
    Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2")); 
    Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2)); 
    Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3")); 
} 

private class SortItem : IComparable<SortItem> 
{ 
    public int SortOrder { get; set; } 
    public string Name { get; set; } 

    public int CompareTo(SortItem other) 
    { 
     return SortOrder.CompareTo(other.SortOrder); 
    } 
} 

In der Testmethode, wenn Sie rufen Sort() -Methode statt SortStable(), Sie kann sehen, dass der Test fehlschlagen würde.

Answer 7

In einigen Anwendungen, wenn eine Liste von Elementen nach einem bestimmten Kriterium sortiert wird, ist es nicht notwendig, die ursprüngliche Reihenfolge der Elemente beizubehalten, die gleichwertig sind. In anderen Anwendungen ist es notwendig. Sortiermethoden, die die Anordnung von Elementen mit übereinstimmenden Schlüsseln ("stabile Sortierungen") beibehalten, sind im Allgemeinen entweder viel langsamer als solche, die dies nicht tun ("instabile Sortierungen"), oder sie benötigen eine erhebliche Menge temporären Speicher (und sind immer noch etwas langsamer Die erste "Standard-Bibliothek" -Sortierroutine, die verbreitet wurde, war wahrscheinlich die qsort()-Funktion, die in der Standard-C-Bibliothek enthalten ist. Diese Bibliothek wurde häufig verwendet, um Listen zu sortieren, die relativ zu der Gesamtmenge an verfügbarem Speicher groß waren waren viel weniger nützlich, wenn es eine Menge an temporärer Speicherung proportional zur Anzahl der Elemente in der zu sortierenden Array benötigt hätte

Sortiermethoden, die unter Frameworks wie Java oder .net verwendet werden könnte praktisch viel nutzen mehr temporärer Speicher als in einem C qsor akzeptabel wäre t() Routine. Eine temporäre Speicheranforderung, die der Größe des zu sortierenden Arrays entspricht, würde in den meisten Fällen kein besonderes Problem darstellen. Da es für Bibliotheken jedoch üblich ist, eine Quicksort-Implementierung zu liefern, scheint dies das Muster zu sein, dem .net folgt.