c# - property - ¿Por qué el método List<T>.Sort reordena los elementos IComparable<T>?

order by list c# linq

Question

Tengo un problema con la forma en que el método de ordenación de listas se ocupa de la clasificación. Dado el siguiente 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);
    }
}

Si trato de ordenar de esta manera:

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

Entonces el primer elemento es el segundo elemento anterior "Segundo". O, en otras palabras, esta afirmación falla:

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

¿Por qué .NET está reordenando mi lista cuando los elementos son esencialmente los mismos? Me gustaría que solo reordene la lista si la comparación devuelve un valor distinto de cero.

Answer 1

Aquí hay un método de extensión SortStable () para la 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);
    }
}

Prueba:

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

En el método de prueba, si llama al método Sort () en lugar de SortStable (), puede ver que la prueba fallará.

Answer 2

De la documentación del método List.Sort () de MSDN:

Este método utiliza Array.Sort, que utiliza el algoritmo QuickSort. Esta implementación realiza una ordenación inestable; es decir, si dos elementos son iguales, su orden podría no conservarse. En contraste, una clasificación estable conserva el orden de los elementos que son iguales.

Aquí está el enlace: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Esencialmente, el ordenamiento se realiza según lo diseñado y documentado.

Answer 3

En algunas aplicaciones, cuando una lista de artículos se clasifica de acuerdo con algún criterio, no es necesario conservar el orden original de los artículos que se comparan igual. En otras aplicaciones, es necesario. Los métodos de clasificación que conservan la disposición de los elementos con claves coincidentes (denominados "clases estables" son generalmente mucho más lentos que aquellos que no lo hacen ("clases inestables"), o bien requieren una cantidad significativa de almacenamiento temporal (y aún son algo más lentos ). La primera rutina de clasificación de "biblioteca estándar" que se generalizó fue probablemente la función qsort() incluida en la biblioteca estándar de C. Esta biblioteca se habría utilizado con frecuencia para ordenar listas que eran grandes en relación con la cantidad total de memoria disponible. La biblioteca habría sido mucho menos útil si hubiera requerido una cantidad de almacenamiento temporal proporcional al número de elementos en la matriz que se ordenará.

Los métodos de clasificación que se utilizarán en marcos como Java o .net podrían hacer uso de mucho más almacenamiento temporal de lo que hubiera sido aceptable en una rutina de C qsort (). Un requisito de memoria temporal igual al tamaño de la matriz que se ordenará en la mayoría de los casos no plantea ningún problema en particular. No obstante, dado que ha sido tradicional que las bibliotecas suministren una implementación de Quicksort, ese parece ser el patrón seguido por .net.

Answer 4

Le dijiste cómo comparar las cosas y así fue. No debe confiar en la implementación interna de Sort en su aplicación. Es por eso que le permite anular el valor de CompareTo. Si desea tener un parámetro de clasificación secundario ("descripción" en este caso), codifíquelo en su CompareTo. Confiar en cómo Sort funciona simplemente es una excelente manera de codificar un error que es muy difícil de encontrar.

Puede encontrar un quicksort estable para .NET o usar una ordenación de fusión (que ya es estable).

Answer 5

Puede solucionar este problema agregando un "valor de índice" a su estructura, e incluyéndolo en el método CompareTo cuando Priority.CompareTo devuelve 0. Luego deberá inicializar el valor de "índice" antes de hacer la clasificación.

El método CompareTo se vería así:

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

Luego, en lugar de hacer elements.Sort() , harías:

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

Answer 6

Si quisiera ordenar en base a dos campos en lugar de uno, podría hacer esto:

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, esto no satisface el requisito de un algoritmo de búsqueda estable; Sin embargo, satisface su afirmación y permite el control de su orden de elementos en caso de igualdad.

Answer 7

Vea las otras respuestas para saber por qué List.Sort () es inestable. Si necesita una clasificación estable y está utilizando .NET 3.5, intente Enumerable.OrderBy() (LINQ).