ArrayList.Sort должен быть стабильным с IComparer, но не так ли? - PullRequest
Новая
       20

ArrayList.Sort должен быть стабильным с IComparer, но не так ли?

7 голосов
/ 19 февраля 2011

A стабильная сортировка - это сортировка, которая поддерживает относительный порядок элементов с одинаковым значением.

В документах по 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
    }
}

Я что-то упустил? Если нет, то будет ли это ошибкой документации или библиотекой?

Видимо, использование OrderBy в Linq дает стабильную сортировку.

1 Ответ

9 голосов
/ 19 февраля 2011

Документация говорит о том, что единственный способ получить стабильную сортировку с помощью ArrayList.Sort - это использовать IComparer, который каким-то образом «знает» индексы сравниваемых элементов (можно предположить,выполняя это, заставляя его выполнить начальную передачу коллекции), и использует эту информацию в качестве прерывателя связей для в противном случае равных элементов.

Хотя я согласен с тем, что формулировка документации оставляет желать лучшего, на самом деле нет никакого смысла в том, чтобы любой старый компаратор, который не считал индексы предметовСравнение может волшебным образом превратить по своей природе нестабильный алгоритм сортировки (что и есть Arraylist.Sort) в стабильный.

...