Почему переупорядочение метода List <T>.Sort соответствует элементам IComparable <T>?

Question

У меня проблема с тем, как метод сортировки списка работает с сортировкой. Учитывая следующий элемент:

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

Тогда первым элементом является ранее второй элемент «Второй». Или, другими словами, это утверждение не выполняется:

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

Почему .NET переупорядочивает мой список, когда элементы по существу одинаковы? Я бы хотел, чтобы он только переупорядочивал список, если сравнение возвращает ненулевое значение.

Answer 1

Из документации метода List.Sort () из MSDN:

Этот метод использует Array.Sort, который использует алгоритм QuickSort. Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраниться. Напротив, стабильная сортировка сохраняет порядок элементов, которые равны.

Вот ссылка: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

По сути, сортировка выполняется так, как задумано и задокументировано.

Answer 2

Вот метод расширения SortStable () для List<T> where T : IComparable<T>:

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

В тестовом методе, если вы вызовете метод Sort () вместо SortStable (), вы увидите, что тест не пройден.

Answer 3

См. Другие ответы о том, почему List.Sort () нестабилен. Если вам нужна стабильная сортировка и вы используете .NET 3.5, попробуйте Enumerable.OrderBy () (LINQ).

Answer 4

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

Вы можете найти стабильную быструю сортировку для .NET или использовать сортировку слиянием (которая уже стабильна).

Answer 5

В некоторых приложениях, когда список элементов сортируется по некоторому критерию, сохранение первоначального порядка элементов, которые сравниваются равными, не требуется. В других приложениях это необходимо. Методы сортировки, которые сохраняют расположение элементов с соответствующими ключами (так называемые "стабильные сортировки", обычно либо намного медленнее, чем те, которые не ("нестабильные сортировки"), либо они требуют значительного объема временного хранения (и все же несколько медленнее Первой подпрограммой сортировки «стандартной библиотеки», которая стала широко распространенной, была, вероятно, функция qsort(), включенная в стандартную библиотеку C. Эта библиотека часто использовалась бы для сортировки списков, которые были большими по отношению к общему объему доступной памяти. библиотека была бы гораздо менее полезной, если бы требовалось количество временного хранилища, пропорциональное количеству элементов в массиве, которые должны быть отсортированы.

Методы сортировки, которые будут использоваться в таких средах, как Java или .net, могут практически использовать гораздо больше временного хранилища, чем было бы приемлемо в подпрограмме C qsort (). Временное требование к памяти, равное размеру сортируемого массива, в большинстве случаев не представляет какой-либо конкретной проблемы. Тем не менее, поскольку библиотеки традиционно предоставляют реализацию Quicksort, похоже, это шаблон, за которым следует .net.

Answer 6

Это можно исправить, добавив «значение индекса» в свою структуру и включив его в метод CompareTo, когда Priority.CompareTo вернет 0. Затем вам потребуется инициализировать значение «индекса» перед выполнением сортировки.

Метод 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();

Answer 7

Если вы хотите отсортировать по двум полям вместо одного, вы можете сделать это:

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

Очевидно, что это не удовлетворяет требованию стабильного алгоритма поиска; Тем не менее, оно удовлетворяет вашему утверждению и позволяет контролировать порядок элементов в случае равенства.