Pourquoi la méthode List & T > .Sort réorganise-t-elle IComparable < T > éléments?

Question

J'ai un problème avec la manière dont la méthode de tri par liste traite le tri. Étant donné 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 le trier de 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 le second, précédemment "Second". Ou, en d'autres termes, cette assertion échoue:

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

Pourquoi .NET réorganise-t-il ma liste alors que les éléments sont essentiellement les mêmes? J'aimerais qu'il ne réorganise la liste que si la comparaison renvoie une valeur non nulle.

Answer 1

Dans la documentation de la méthode List.Sort () à partir de MSDN:

  

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, une sorte stable préserve l’ordre des éléments égaux.

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

Le tri s'effectue essentiellement comme prévu et documenté.

Answer 2

Voici une méthode d'extension SortStable () pour Liste < T > où 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 de test, si vous appelez la méthode Sort () au lieu de SortStable (), vous pouvez voir que le test échouera.

Answer 3

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

Vous pouvez trouver un quicksort stable pour .NET ou utiliser un type de fusion (qui est déjà stable).

Answer 4

Voir les autres réponses pour savoir pourquoi List.Sort () est instable. Si vous avez besoin d’un tri stable et que vous utilisez .NET 3.5, essayez Enumerable.OrderBy ( ) (LINQ).

Answer 5

Vous pouvez résoudre ce problème en ajoutant une " valeur d'index " à votre structure et en incluant cela dans la méthode CompareTo lorsque Priority.CompareTo renvoie 0. Vous devez ensuite initialiser le paramètre "index". valeur 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;
}

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

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

Answer 6

Dans certaines applications, lorsqu'une liste d'éléments est triée en fonction d'un critère, il est inutile de conserver l'ordre d'origine des éléments qui se comparent. Dans d'autres applications, c'est nécessaire. Les méthodes de tri qui préservent la disposition des éléments avec des clés correspondantes (appelées "sortes stables") sont généralement beaucoup plus lentes que celles qui ne le sont pas ("sortes instables"), ou bien elles nécessitent une quantité importante de stockage temporaire (et sont toujours en attente). La première routine de tri "bibliothèque standard" à se généraliser était probablement la fonction qsort () incluse dans la bibliothèque standard C. Cette bibliothèque aurait souvent été utilisée pour trier des listes volumineuses. Par rapport à la quantité totale de mémoire disponible, la bibliothèque aurait été beaucoup moins utile si elle avait nécessité une quantité de mémoire de stockage temporaire proportionnelle au nombre d’éléments du tableau à trier.

Les méthodes de tri qui seront utilisées dans des environnements tels que Java ou .net pourraient faire appel à beaucoup plus de mémoire de stockage temporaire qu’elle n’aurait été acceptable dans une routine C qsort (). 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 de tradition que les bibliothèques fournissent une implémentation Quicksort, il semble que ce soit le modèle suivi par .net.

Answer 7

Si vous souhaitez effectuer un tri en fonction de 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);
        }
    }
}

Évidemment, cela ne satisfait pas à l'exigence d'un algorithme de recherche stable; Cependant, cela satisfait votre assertion et permet de contrôler l'ordre de vos éléments en cas d'égalité.