Почему метод List<T>.Sort изменяет порядок равных несопоставимых<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();

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

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

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

Answer 1

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

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

Вот ссылка: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

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

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

Answer 4

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

Answer 5

Вы можете исправить это, добавив "значение индекса" в свою структуру и включив его в метод compareTo при приоритете.compareTo возвращает 0.Затем вам нужно будет инициализировать значение "index", прежде чем выполнять сортировку.

Метод сравнения будет выглядеть следующим образом:

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 6

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

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

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

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