¿Por qué la lista <T>. Método de ordenar reordenar elementos iguales de IComparable <T>?

Question

Tengo un problema con la forma en que el método List Sort trata con 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 intento para solucionar el problema 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(); 

A continuación, el primer elemento es el previamente segundo elemento "Segundo". O, en otras palabras, esta afirmación no:

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

¿Por qué se .NET reordenamiento 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 de QuickSort. Esta implementación realiza una clasificación inestable; es decir, si dos elementos son iguales, es posible que su orden no se conserve. Por el contrario, un género estable conserva el orden de los elementos que son iguales.

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

En esencia, el tipo está funcionando como fue diseñado y documentado.

Answer 2

Usted le dijo cómo comparar cosas y lo hizo. No debe confiar en la implementación interna de Sort en su aplicación. Es por eso que le permite anular 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 funciona Sort 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 merge sort (que ya es estable).

Answer 3

Puede solucionar esto agregando un "valor de índice" a su estructura, e incluyendo eso en el método CompareTo cuando Priority.CompareTo devuelve 0. Entonces necesitaría inicializar el valor de "índice" 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; 
} 

Entonces, en lugar de hacer elements.Sort(), puede hacer:

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

Answer 4

Ver las otras respuestas de por qué list.sort() es inestable. Si necesita una clasificación estable y usa .NET 3.5, intente Enumerable.OrderBy() (LINQ).

Answer 5

Si queremos ordenar basado en dos campos en lugar de uno que 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 6

Aquí es un método de extensión 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); 
    } 
} 

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 ensayo, si se llama método sort() en lugar de SortStable(), se puede ver que la prueba fallará

Answer 7

En algunas aplicaciones, cuando se ordena una lista de elementos de acuerdo con algún criterio, no es necesario conservar el orden original de los elementos que se comparan iguales. En otras aplicaciones, es necesario. Los métodos de clasificación que conservan la disposición de elementos con claves coincidentes (llamados "géneros estables" generalmente son mucho más lentos que los que no ("géneros inestables") o 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" se generalizó probablemente fue la función qsort() incluida en la biblioteca estándar C. Esa biblioteca se habría utilizado con frecuencia para ordenar listas que eran grandes en relación con la cantidad total de memoria disponible. han sido mucho menos útiles si se hubiera requerido una cantidad de almacenamiento temporal proporcional al número de elementos en la matriz que se va a ordenar.

Los métodos de clasificación que se utilizarán en frameworks como Java o .net podrían hacer prácticamente uso de mucho almacenamiento más temporal que habría sido aceptable en un C qsor t() rutina. Un requisito de memoria temporal igual al tamaño de la matriz que se va a ordenar, en la mayoría de los casos, no plantearía 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.