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

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

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 переупорядочивает мой список, когда элементы по существу одинаковы? Я бы хотел, чтобы он только изменил порядок списка, если сравнение возвращает ненулевое значение.

Ответ 1

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

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

Здесь ссылка: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

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

Ответ 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(), вы можете увидеть, что тест завершится с ошибкой.

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

Ответ 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);
        }
    }
}

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