¿Por qué el método List < T > .Sort reordena IComparable < T > ¿elementos?

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

Luego, el primer elemento es el segundo elemento anteriormente " 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

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 ordenació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, la clasificación se está realizando según lo diseñado y documentado.

Answer 2

Aquí hay un método de extensión SortStable () para List < T > donde 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ía.

Answer 3

Le dijiste cómo comparar las cosas y lo hizo. No debe confiar en la implementación interna de Sort en su aplicación. Es por eso que te 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 simplemente funciona es una excelente manera de codificar un error que es muy difícil de encontrar.

Puede encontrar un quicksort estable para .NET o usar un combinar clasificación (que ya es estable).

Answer 4

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).

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. A continuación, deberá inicializar el " índice " Valor antes de hacer el ordenamiento.

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

En algunas aplicaciones, cuando una lista de elementos se clasifica de acuerdo con algún criterio, no es necesario conservar el orden original de los elementos 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 los que no lo hacen ("clases inestables"), o bien requieren una cantidad significativa de almacenamiento temporal (y aún son algo más lento). La primera rutina de clasificación de la "biblioteca estándar" que se extendió 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 usarán en marcos como Java o .net prácticamente podrían hacer uso de mucho más almacenamiento temporal de lo que hubiera sido aceptable en una rutina 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 7

Si desea ordenar en función de dos campos en lugar de uno, puede 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.