Warum funktioniert List .Sort Methode Neuordnungs gleich IComparable Elemente?

Question

Ich habe ein Problem mit, wie die Liste Sort-Methode behandelt zu sortieren. In Anbetracht der folgenden 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 für sie nur die Liste neu anordnen, 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 Art; das heißt, wenn zwei Elemente gleich sind, können ihre Bestellung nicht erhalten werden. Im Gegensatz dazu erhält eine stabile Art, die Reihenfolge der Elemente, 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 werden.

Answer 2

Hier 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 () können Sie sehen, dass der Test fehlschlagen würde.

Answer 3

Sie gesagt, dass es, wie die Dinge zu vergleichen, und es tat. Sie sollten sich nicht auf interne Umsetzung Sortieren in der Anwendung verlassen. Deshalb ist es ließ uns Sie CompareTo außer Kraft setzen. Wenn Sie einen sekundären Sortierparameter haben ( „Beschreibung“ in diesem Fall), Code in Ihre CompareTo. Unter Berufung auf wie Sortieren passiert einfach zu arbeiten ist eine gute Möglichkeit, in einem Fehler zu codieren, die sehr schwer zu finden ist.

Sie können eine stabile quicksort für .NET finden oder verwenden Sie eine Art verschmelzen (die bereits stabil ist).

Answer 4

Sehen Sie die anderen Antworten, warum List.Sort () ist instabil. Wenn Sie eine stabile Art benötigen, und werden mit .NET 3.5, versuchen Enumerable.OrderBy ( ) (LINQ).

Answer 5

Sie können dieses Problem beheben, indem sie einen „Index-Wert“, um Ihre Struktur hinzufügen und einschließlich dem in der CompareTo Methode, wenn Priority.CompareTo 0 zurück Sie dann den „index“ Wert initialisieren müssen würden die Art vor zu tun.

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 6

Bei einigen Anwendungen, wenn eine Liste von Elementen nach einem gewissen Kriterium sortiert ist, die ursprüngliche Reihenfolge der Elemente zu bewahren, die zu vergleichen, gleich unnötig ist. Bei anderen Anwendungen ist es notwendig. Sortierverfahren, die die Anordnung der Elemente mit passenden Schlüssel (so genannte „stabile Sorten“ sind in der Regel entweder viel langsamer als diejenigen erhalten, die dies nicht tun ( „unstable Sorten“), oder aber sie erfordern eine erhebliche Menge an temporären Speicher (und sind immer noch etwas langsamer ). die erste „Standard-Bibliothek“ Sortierroutine verbreitet zu werden war wahrscheinlich die qsort() Funktion in der Standard-C-Bibliothek enthalten. Diese Bibliothek häufig Listen verwendet worden wäre, zu sortieren, die groß im Verhältnis zur Gesamtmenge an Speicher zur Verfügung stehen. die Bibliothek würde haben sehr viel weniger nützlich gewesen, wenn es eine Menge an temporären Speichern proportional zu der Anzahl der Elemente im Array erforderlich war sortiert werden.

Sortieren Methoden, die unter Frameworks wie Java oder .net verwendet werden, praktisch Verwendung von viel mehr temporären Speichern machen könnte, als in einem C qsort () Routine akzeptabel gewesen wäre. Ein temporärer Speicherbedarf gleich die Größe des Arrays sortiert werden würde in den meisten Fällen kein besonderes Problem darstellen. Dennoch eine Quicksort Implementierung zu liefern, da es für Bibliotheken traditionell gewesen ist, das scheint das Muster von .net gefolgt zu sein.

Answer 7

Wenn Sie wollen statt einem auf zwei Felder sortieren Sie dies tun könnten:

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, dass dies nicht die Anforderung eines stabilen Suchalgorithmus erfüllen; Allerdings ist es Ihre Behauptung erfüllen, und ermöglicht die Kontrolle über Ihr Element, um im Fall der Gleichheit.