[C# 2.0] Comment implementer un Tri stable pour un List<T> ?

Version imprimable

14/05/2006, 14h16
margagn

[C# 2.0] Comment implementer un Tri stable pour un List<T> ?

Bonjour !

J’ai un petit (ou gros…) problème de tri. J’ai un List<T> et chaque élément correspond à une classe qui contient au moins deux informations visibles sur lesquelles je dois faire un tri. Ma première idée a été d’utiliser le List<T>.Sort. Le problème est que ce tri n’est pas stable (c.-à-d. qu'il garde l'ordre relatif des quantités égales pour la relation d'ordre).

Est-ce que .NET ou quelqu’un à quelque part à déjà implanté un tri stable en .NET du style d’utilisation du Sort de Microsoft ? Dois-je sortir un livre d’algo et le coder moi-même? Je ne peux pas croire qu’il n’y a pas une solution simple ou que Microsoft n’a pas pensé à ça…

Merci beaucoup de votre aide !

Martin
14/05/2006, 14h35
Kikos31

Citation:

Envoyé par margagn

Ma première idée a été d’utiliser le List<T>.Sort. Le problème est que ce tri n’est pas stable (c.-à-d. qu'il garde l'ordre relatif des quantités égales pour la relation d'ordre).

Est-ce que .NET ou quelqu’un à quelque part à déjà implanté un tri stable en .NET du style d’utilisation du Sort de Microsoft ?

Lorsque tu implémente la methode compare tu peux prendre un critère secondaire pour éviter d'avoir 2 membres strictements identiques dans ton tri.
14/05/2006, 15h30
margagn

Bonjour Kikos31,

Est-ce que tu as un exemple ? Je ne suis pas certain de comprendre... :oops:

Merci !

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
 
namespace ConsoleApplication1
{
    class A : IComparable
    {
        int a, b;
 
        public A(int a, int b) {
            this.a = a;
            this.b = b;
        }
 
        public override string ToString() {
            return "( " + a + " , " + b + " )";
        }
 
        #region IComparable Membres
 
        public int CompareTo(object obj) {
            A other = obj as A;
            if (other == null)
                throw new ArgumentException("obj is not a A.");
            if (a != other.b)
                return a - other.a;
            else
                return b - other.b;
        }
 
        #endregion
    }
 
    class Program
    {
        static void Main(string [] args) {
            List<A> list = new List<A>();
            list.Add(new A(5, 1));
            list.Add(new A(4, 10));
            list.Add(new A(5, -50));
 
            Console.WriteLine("Unsorted :");
            foreach (A a in list)
                Console.WriteLine(a.ToString());
            list.Sort();
 
            Console.WriteLine("Sorted : ");
            foreach (A a in list)
                Console.WriteLine(a.ToString());
            Console.ReadKey();
        }
    }
}

Ou en plus court si les valeurs à comparer sont accessibles de l'extérieur, qu'on ne veut pas mettre la comparaison dans la classe (si ça dépend du code client) ou qu'on ne peut pas la modifier :
Code:

1 2 3 4 5 6 7 8 9 10 11 list.Sort( delegate( A x, A y ) { if ( x.Value1 != y.Value1 ) { return x.Value1.CompareTo( y.Value1 ); } return x.Value2.CompareTo( y.Value2 ); } );
Dans tous les cas le principe est le même. Pour avoir un tri qui donne un résultat prévisible, il faut que la comparaison se fasse sur autant de critères qu'il faut pour que deux éléments ne soient pas identiques (ou que ça n'ait pas d'importance).

14/05/2006, 22h52
margagn

Ca fonctionne ! :D Fantastique !

Merci beaucoup de votre aide !
13/02/2008, 16h49
StefC30

Type nullable

En effet, c'est la bonne solution pour effectuer des tris.

Le problème reste posé avec les types nullables (int? , DateTime? etc...) :(

On ne peut implémenter CompareTo avec ces types, alors comment faire ?

@+

Stéphan.
14/02/2008, 10h35
StefC30

Solution

Je pense avoir la solution. :D

Code:

int Nullable.Compare<T>(Nullable<T>, Nullable<T>)

On peut donc comparer les types nullables de manière générique.

Dans la méthode IComparable CompareTo qui fournit l'ordre de tri par défaut pour .sort() il suffit de faire :

Code:

return Nullable.Compare<letype>(objet1.propriete, objet2.propriete)

Où "letype" est un int, DateTime, Decimal...

Il est même possible de ne pas préciser le type T en question :

Code:

return Nullable.Compare(objet1.propriete, objet2.propriete)

Si je fais erreur, merci de me corriger ;)

@+

Stéphan.
05/03/2008, 15h09
awd

Après 10 minutes de recherche pour réussir à comparer des types nullables. J'ai trouvé la solution dans ce post !

Je confirme la solution est la suivante :

Code:

return Nullable.Compare<letype>(objet1.propriete, objet2.propriete)

1000 fois merci :)
Alexandre