Pourquoi la méthode <T> .Sort réorganiser égale IComparable <T> éléments?

Question

J'ai un problème avec la façon dont la méthode de tri par liste gère le tri. Compte tenu de l'élément suivant:

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 j'essaie de trier cette façon:

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

Ensuite, le premier élément est l'élément précédemment deuxième « deuxième ». Ou, en d'autres termes, cette assertion échoue:

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

Pourquoi .NET ReOrdering ma liste lorsque les éléments sont essentiellement les mêmes? Je voudrais seulement réorganiser la liste si la comparaison renvoie une valeur non nulle.

Answer 1

De la documentation de la méthode de MSDN list.sort():

Cette méthode utilise Array.Sort, qui utilise l'algorithme QuickSort. Cette implémentation effectue un tri instable; c'est-à-dire que si deux éléments sont égaux, leur ordre pourrait ne pas être conservé. En revanche, un tri stable préserve l'ordre des éléments égaux.

Voici le lien: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Essentiellement, le genre fonctionne comme conçu et documenté.

Answer 2

Vous lui avez dit comment comparer les choses et il l'a fait. Vous ne devez pas compter sur l'implémentation interne de Sort dans votre application. C'est pourquoi il vous permet de remplacer CompareTo. Si vous voulez avoir un paramètre de tri secondaire ("description" dans ce cas), codez-le dans votre CompareTo. S'appuyer sur le mode de fonctionnement de Sort est un excellent moyen de coder un bogue très difficile à trouver.

Vous pouvez trouver un port de synchronisation stable pour .NET ou utiliser un merge sort (qui est déjà stable).

Answer 3

Vous pouvez corriger cela en ajoutant une "valeur d'index" à votre structure, et en incluant cela dans la méthode CompareTo lorsque Priority.CompareTo renvoie 0. Vous devrez alors initialiser la valeur "index" avant de faire le tri.

La méthode CompareTo ressemblerait à ceci:

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

Alors, au lieu de faire elements.Sort(), vous feriez:

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

Answer 4

Voir les autres réponses pour lesquelles list.sort() est instable. Si vous avez besoin d'un tri stable et utilisez .NET 3.5, essayez Enumerable.OrderBy() (LINQ).

Answer 5

Si vous voulez un tri sur deux champs au lieu d'un, vous pouvez le faire:

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

De toute évidence, cela ne satisfait pas à l'exigence d'un algorithme de recherche stable; Cependant, il satisfait votre assertion, et permet le contrôle de l'ordre de vos éléments en cas d'égalité.

Answer 6

Voici une méthode d'extension SortStable() pour 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); 
    } 
} 

Dans la méthode d'essai, si vous appelez Trier() au lieu de SortStable(), vous peut voir que le test échouerait.

Answer 7

Dans certaines applications, lorsqu'une liste d'éléments est triée en fonction de certains critères, il n'est pas nécessaire de préserver l'ordre d'origine des éléments qui sont égaux. Dans d'autres applications, c'est nécessaire. Les méthodes de tri qui conservent la disposition des éléments avec des clés correspondantes (appelées «tris stables» sont généralement beaucoup plus lentes que celles qui ne le sont pas («tris instables»), ou nécessitent une quantité importante de stockage temporaire (et sont encore un peu plus lentes La première routine de tri de «bibliothèque standard» à se répandre était probablement la fonction qsort() incluse dans la bibliothèque C standard, qui était fréquemment utilisée pour trier les listes qui étaient grandes par rapport à la quantité totale de mémoire disponible. ont été beaucoup moins utiles si cela avait nécessité une quantité de stockage temporaire proportionnelle au nombre d'éléments dans le tableau à trier

Les méthodes de tri qui seront utilisées sous des frameworks comme Java ou .net pourraient pratiquement faire appel à beaucoup de choses. plus de stockage temporaire que ce qui aurait été acceptable dans un C t() routine. Une exigence de mémoire temporaire égale à la taille du tableau à trier ne poserait dans la plupart des cas aucun problème particulier. Néanmoins, comme il est traditionnel pour les bibliothèques de fournir une implémentation Quicksort, cela semble être le modèle suivi par .net.