List＆lt; T＆gt; .SortメソッドがIComparable＆lt; T＆gt;と等しい順序で並べ替える理由要素？

StackOverflow https://stackoverflow.com/questions/800007

  •  03-07-2019
  •  | 
  •  

質問

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番目の要素＆quot; Second＆quot;です。または、言い換えると、このアサーションは失敗します：

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

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

役に立ちましたか？

解決

MSDNのList.Sort（）メソッドのドキュメントから：

  

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

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

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

他のヒント

List＆lt; T＆gt;の拡張メソッドSortStable（）です。 T：IComparable＆lt; T＆gt; ：

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（）メソッドを呼び出すと、テストが失敗することがわかります。

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

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

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

「インデックス値」を追加することでこれを修正できます; 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();

一部のアプリケーションでは、アイテムのリストが何らかの基準に従ってソートされる場合、等しいと比較するアイテムの元の順序を維持する必要はありません。他のアプリケーションでは必要です。一致するキーを持つアイテムの配置を保持するソート方法（「安定したソート」と呼ばれるものは一般に、そうでないものよりも非常に遅い（「不安定なソート」））、またはかなりの量の一時ストレージを必要としますやや遅い）最初の「標準ライブラリ」ソートルーチンが普及したのは、おそらく標準Cライブラリに含まれる qsort（）関数だった。配列内のアイテムの数に比例する一時ストレージをソートする必要がある場合、ライブラリはあまり有用ではありませんでした。

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

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

明らかに、これは安定した検索アルゴリズムの要件を満たしていません。ただし、これはアサーションを満たし、平等の場合に要素の順序を制御できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top