28

List Sort メソッドがソートを処理する方法に問題があります。次の要素があるとします。

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

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

このように並べ替えようとすると、次のようになります。

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();

次に、最初の要素は、前の 2 番目の要素「Second」です。または、言い換えると、このアサーションは失敗します。

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

要素が本質的に同じであるのに、.NET がリストを並べ替えるのはなぜですか? 比較でゼロ以外の値が返された場合にのみ、リストを並べ替えたいと思います。

4

7 に答える 7

44

MSDN の List.Sort() メソッドのドキュメントから:

このメソッドは、QuickSort アルゴリズムを使用する Array.Sort を使用します。この実装は、不安定な並べ替えを実行します。つまり、2 つの要素が等しい場合、それらの順序は保持されない可能性があります。対照的に、安定した並べ替えは、等しい要素の順序を保持します。

リンクは次のとおりです 。 http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

基本的に、ソートは設計および文書化されたとおりに実行されます。

于 2009-04-28T22:03:13.157 に答える
7

の拡張メソッド SortStable() を次に示し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]
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);
    }
}

テスト メソッドで、SortStable() の代わりに Sort() メソッドを呼び出すと、テストが失敗することがわかります。

于 2012-05-04T13:31:14.423 に答える
3

List.Sort（）が不安定である理由については、他の応答を参照してください。安定した並べ替えが必要で、.NET 3.5を使用している場合は、Enumerable.OrderBy（）（LINQ）を試してください。

于 2009-04-28T22:15:28.057 に答える
3

あなたは物事を比較する方法を教えてくれました。アプリケーションでの Sort の内部実装に依存しないでください。そのため、CompareTo をオーバーライドできます。2 番目の並べ替えパラメーター (この場合は「説明」) が必要な場合は、それを CompareTo にコーディングします。Sort がたまたま機能する方法に依存することは、見つけるのが非常に困難なバグをコーディングするための優れた方法です。

.NET 用の安定したクイックソートを見つけるか、(既に安定している)マージ ソートを使用できます。

于 2009-04-28T22:02:02.130 に答える
1

これを修正するには、構造に「インデックス値」を追加し、Priority.CompareToが0を返すときにCompareToメソッドに含めます。次に、並べ替えを行う前に「インデックス」値を初期化する必要があります。

CompareToメソッドは次のようになります。

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

次に、を行う代わりに、次のelements.Sort()ようにします。

for(int i = 0; i < elements.Count; ++i)
{
    elements[i].Index = i;
}
elements.Sort();
于 2009-04-28T22:13:51.757 に答える
1

一部のアプリケーションでは、アイテムのリストが何らかの基準に従ってソートされている場合、同等のアイテムの元の順序を維持する必要はありません。他のアプリケーションでは必要です。一致するキーを持つアイテムの配置を保持するソート方法 (「安定ソート」と呼ばれる) は、一般に、そうでないもの (「不安定ソート」) よりもはるかに遅くなるか、大量の一時ストレージが必要になります (それでも多少遅くなります)。 ) 広く普及した最初の「標準ライブラリ」ソートルーチンは、おそらくqsort()標準 C ライブラリに含まれる関数。そのライブラリは、使用可能なメモリの総量に比べて大きいリストをソートするために頻繁に使用されていました。ライブラリは、並べ替える配列内のアイテムの数に比例した量の一時ストレージを必要とした場合、あまり役に立たなかったでしょう。

Java や .net などのフレームワークで使用されるソート メソッドは、実際には、C の qsort() ルーチンで許容されるよりもはるかに多くの一時ストレージを使用できます。ソートされる配列のサイズに等しい一時メモリー要件は、ほとんどの場合、特別な問題を引き起こすことはありません。とはいえ、ライブラリが Quicksort の実装を提供するのは伝統的なことなので、これは .net が従うパターンのようです。

于 2012-05-04T15:55:51.603 に答える
0

1 つではなく 2 つのフィールドに基づいて並べ替えたい場合は、次のようにします。

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);
        }
    }
}

明らかに、これは安定した検索アルゴリズムの要件を満たしていません。ただし、それはあなたの主張を満たし、等しい場合に要素の順序を制御できます。

于 2009-04-28T22:24:40.857 に答える