Por que List .Sort método reordenar iguais IComparable elementos?

Question

Eu tenho um problema com a forma como a lista Classificar método lida com a classificação. Dado o seguinte elemento:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        return Priority.CompareTo(other.Priority);
    }
}

Se eu tentar classificá-lo desta maneira:

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

Em seguida, o primeiro elemento é o anteriormente segundo elemento de "Segundo". Ou, em outras palavras, esta afirmação falhar:

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

Por que é .NET reordenação minha lista quando os elementos são essencialmente os mesmos? Eu gostaria que ele apenas reordenar a lista, se a comparação retorna um valor diferente de zero.

Answer 1

A partir da documentação do método list.sort () do MSDN:

Este método usa Array.Sort, que usa o algoritmo QuickSort. Esta implementação realiza uma espécie instável; isto é, se dois elementos são iguais, a ordem pode não ser preservada. Em contraste, um estábulo tipo preserva a ordem dos elementos que são iguais.

Aqui está o link: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Essencialmente, o tipo está funcionando como projetado e documentado.

Answer 2

Aqui está um método de extensão SortStable () para 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:

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

No método de teste, se você chamar Sort () método em vez de SortStable (), você pode ver que o teste seria um fracasso.

Answer 3

Você disse que como comparar coisas e ele fez. Você não deve confiar em implementação interna de Sort em sua aplicação. É por isso que lhe permite substituir CompareTo. Se você quer ter um parâmetro de classificação secundária ( "descrição", neste caso), código-lo em seu CompareTo. Baseando-se como Sort só acontece de trabalho é uma ótima maneira de código em um bug que é muito difícil de encontrar.

Você poderia encontrar um quicksort estável para .NET ou usar um merge sort (o qual já é estável).

Answer 4

Veja as outras respostas para o porquê list.sort () é instável. Se você precisar de uma espécie estável e estão usando .NET 3.5, tente Enumerable.OrderBy ( ) (LINQ).

Answer 5

Você pode corrigir isso adicionando um "valor do índice" à sua estrutura, e inclusive que no método CompareTo quando Priority.CompareTo retorna 0. Você, então, precisa inicializar o valor "index" antes de fazer o tipo.

O método CompareTo ficaria assim:

public int CompareTo(Element other)
{
    var ret = Priority.CompareTo(other.Priority);
    if (ret == 0)
    {
        ret = Comparer<int>.Default.Compare(Index, other.Index);
    }
    return ret;
}

Em seguida, em vez de fazer elements.Sort(), você faria:

for(int i = 0; i < elements.Count; ++i)
{
    elements[i].Index = i;
}
elements.Sort();

Answer 6

Em algumas aplicações, quando uma lista de itens é classificada de acordo com algum critério, preservando a ordem original dos itens que comparam iguais é desnecessário. Em outras aplicações, é necessário. Ordenar métodos que preservam a disposição dos itens com chaves de correspondência (chamados de "tipos estáveis" são geralmente quer muito mais lento do que aqueles que não o fazem ( "tipos instáveis"), ou então eles exigem uma quantidade significativa de armazenamento temporário (e ainda são um pouco mais lento ). a primeira "biblioteca padrão" tipo de rotina para se tornar generalizada foi, provavelmente, a função qsort() incluído na biblioteca C padrão. essa biblioteca que freqüentemente têm sido utilizados para listas de classificação que eram grande em relação à quantidade total de memória disponível. a biblioteca têm sido muito menos útil se tivesse exigido uma quantidade de proporcional armazenamento temporário para o número de itens na matriz para ser classificado.

Classificar os métodos que serão utilizados no âmbito de quadros como Java ou .net praticamente podia fazer uso de armazenamento muito mais temporário do que teria sido aceitável em um qsort C (de rotina). Um requisito de memória temporária igual ao tamanho da matriz para ser resolvido seria na maioria dos casos não representam qualquer problema particular. No entanto, uma vez que tem sido tradicional para as bibliotecas para fornecer uma implementação Quicksort, que parece ser o padrão seguido por NET.

Answer 7

Se você quiser classificar com base em dois campos em vez de um que você poderia fazer isso:

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

Obviamente, isso não satisfaz a exigência de um algoritmo de busca estável; No entanto, não satisfazer a sua afirmação, e permite o controle de seu elemento de ordem em caso de igualdade.