Discussion :

[margagn]

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

[Kikos31]

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.

[margagn]

Bonjour Kikos31,

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

Merci !

[davcha]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Maniak]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[margagn]

Ca fonctionne ! Fantastique !

Merci beaucoup de votre aide !