7

安定ソートは、同じ値を持つ要素の相対的な順序を維持するソートです。

ArrayList.Sortのドキュメントによると、IComparerが提供されている場合、並べ替えは安定しています。

comparerがnullに設定されている場合、このメソッドは比較ソート（不安定ソートとも呼ばれます）を実行します。つまり、2つの要素が等しい場合、それらの順序は保持されない可能性があります。対照的に、安定ソートでは、等しい要素の順序が保持されます。安定したソートを実行するには、カスタムIComparerインターフェースを実装する必要があります。

何かが足りない場合を除いて、次のテストケースはArrayList.Sort、安定ソートを使用していないことを示しています。

internal class DisplayOrdered {
    public int ID { get; set; }
    public int DisplayOrder { get; set; }
    public override string ToString() {
        return string.Format("ID: {0}, DisplayOrder: {1}", ID, DisplayOrder);
    }
}

internal class DisplayOrderedComparer : IComparer {
    public int Compare(object x, object y) {
        return ((DisplayOrdered)x).DisplayOrder - ((DisplayOrdered)y).DisplayOrder;
    }
}

[TestFixture]
public class ArrayListStableSortTest {

    [Test]
    public void TestWeblinkCallArrayListIsSortedUsingStableSort() {
        var call1 = new DisplayOrdered {ID = 1, DisplayOrder = 0};
        var call2 = new DisplayOrdered {ID = 2, DisplayOrder = 0};
        var call3 = new DisplayOrdered {ID = 3, DisplayOrder = 2};
        var list = new ArrayList {call1, call2, call3};

        list.Sort(new DisplayOrderedComparer());

        // expected order (by ID): 1, 2, 3 (because the DisplayOrder
        // is equal for ID's 1 and 2, their ordering should be
        // maintained for a stable sort.)
        Assert.AreEqual(call1, list[0]); // Actual: ID=2 ** FAILS 
        Assert.AreEqual(call2, list[1]); // Actual: ID=1
        Assert.AreEqual(call3, list[2]); // Actual: ID=3
    }
}

私は何かが足りないのですか？そうでない場合、これはドキュメントのバグですか、それともライブラリのバグですか？

どうやらLinqでOrderByを使用すると、安定したソートが得られます。

4

1 に答える 1

9

ドキュメントが言っているように見えるのは、安定したソートを取得できる唯一の方法は、比較されているアイテムのインデックスを何らかの形で「知っている」ものArrayList.Sortを使用することです（最初のパスを実行することでこれを達成することを想像できます）IComparerコレクション上で）、他の点では等しい要素のタイブレーカーとしてその情報を使用します。

ドキュメントの言い回しには多くの要望が残されていることに同意しますが、比較対象のアイテムのインデックスを考慮しない古い比較者が、本質的に不安定な並べ替えアルゴリズムを魔法のように変えることができるということは、実際には意味がありません。何ですかArraylist.Sort）安定したものに。

于 2011-02-18T23:24:10.843 に答える