Стабильная сортировка - это сортировка, которая поддерживает относительный порядок элементов с одним и тем же значением.
В документации по ArrayList.Sort говорится, что когда IComparer
при условии, что сортировка является стабильной:
Если для параметра comparer установлено значение NULL, этот метод выполняет сортировку сравнения (также называемую нестабильной сортировкой); то есть, если два элемента равны, их порядок может не сохраниться. Напротив, стабильная сортировка сохраняет порядок равных элементов. Для выполнения стабильной сортировки вы должны реализовать собственный интерфейс 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
}
}
Am I чего-то не хватает? Если не, будет ли это ошибка документации или библиотеки?
Очевидно, использование OrderBy в Linq дает стабильную сортировку.