C# - Default Comparer не работает должным образом при сортировке одного списка другим

Question

У меня есть два списка следующим образом (это упрощенный пример):

var dataList = new List<char>{ 'a', 'b', 'c', 'd', 'e', 'f' };
var sortList = new List<int>{ 6, 5, 4, 3, 2, 1 };

Вот как выглядит мой метод сортировки:

void SortOneListByAnother<T1, T2>(List<T1> dataList, List<T2> sortList)
    where T1 : IComparable
    where T2 : IComparable
{
    dataList.Sort((a, b) => sortList[dataList.IndexOf(a)].CompareTo(sortList[dataList.IndexOf(b)]));
}

Это должно вернуть dataList (список символов), отсортированный так же, как sortList (в данном случае, в обратном порядке), то есть:

{ 'f', 'e', 'd', 'c', 'b', 'a' }

Вместо этого мой код, кажется, игнорирует первый и последний элементы списка (при правильной сортировке всего между ними); таким образом я получаю:

{ 'a', 'e', 'd', 'c', 'b', 'f' }

Что я мог делать не так?

Answer 1

Я думаю, что проблема здесь в том, что List.Sort выполняет сортировку на месте, поэтому, когда ваше сравнение вызывает dataList.IndexOf(a)элементы уже частично отсортированы, поэтому вы получаете неопределенное поведение.

Вам нужно сделать копию исходного dataList и использовать его для поиска индекса во время сортировки.

Образец кода:

void SortOneListByAnother<T1, T2>(List<T1> dataList, List<T2> sortList)
    where T1 : IComparable
    where T2 : IComparable
{
    var lookupList = new List<T1>(dataList);
    dataList.Sort((a, b) => sortList[lookupList.IndexOf(a)].CompareTo(sortList[lookupList.IndexOf(b)]));
}

Следует отметить, что этот алгоритм сортировки, вероятно, имеет O(n^3) сложность времени в худшем случае.