Quelques raccourcis :

C# – Tri

Le tri est l'un des problèmes les plus étudiés de l'histoire de l'informatique, et cet article ne vise pas à épuiser la question (loin de là!).

Ce qui est visé ici est un survol rapide d'algorithmes naïfs, un exemple d'algorithme plus sophistiqué, et un survol de la méthode Array.Sort de C# pour voir comment il est possible de réaliser un tri de tableau efficace et relativement générique. Notez que pour aborder des solutions véritablement générales au problème du tri, C# n'est probablement pas le meilleur langage à envisager; il existe des alternatives plus puissantes et plus flexibles).

Tri à bulles

Le tri à bulles est un tri naïf et inefficace... sauf s'il n'y a qu'un très petit nombre d'éléments à trier! Sa plus grand qualité est qu'il est simple à expliquer. En gros :

Le code suit. Dans la fonction TriBulles, le compteur i est la main gauche et le compteur j est la main droite.

using System;
public class Program
{
   static void Permuter(ref int a, ref int b)
   {
      int temp = a;
      a = b;
      b = temp;
   }
   static void TriBulles(int [] vals)
   {
      for(int i = 0; i < vals.Length - 1; ++i)
         for(int j = i + 1; j < vals.Length; ++j)
            if(vals[j] < vals[i])
               Permuter(ref vals[i], ref vals[j]);
   }
   static void Afficher(int []tab)
   {
      for(int i = 0; i != tab.Length; ++i)
         Console.Write($"{tab[i]} ");
      if (EstTrié(tab))
         Console.WriteLine("... il est donc trié");
      else
         Console.WriteLine("... il n'est donc pas trié");
   }
   static bool EstTrié(int [] tab)
   {
      bool résultat = true;
      if (tab.Length > 1)
      {
         for(int i = 1; i != tab.Length; ++i)
            if (tab[i] < tab[i-1])
               résultat = false;
      }
      return résultat;
   }
   static void TestTri(int [] tab)
   {
      Console.Write("Avant : ");
      Afficher(tab);
      TriBulles(tab);
      Console.Write("Après : ");
      Afficher(tab);
   }
   public static void Main()
   {
      TestTri(new int[]{}); // tableau vide
      TestTri(new int[]{ 1,2,3,4,5 }); // tableau déjà trié
      TestTri(new int[]{ 5,1,4,2,3 }); // tableau en désordre, taille impaire
      TestTri(new int[]{ 5,1,6,4,2,3 }); // tableau en désordre, taille paire
   }
}

Le problème de cet algorithme est que pour éléments, on bouge la main gauche fois, et pour chaque positionnement de la main gauche on fait parcourir tout ce qui reste à la main droite. Sur le plan de la complexité algorithmique, on a donc entre opérations dans le meilleur cas (aucune permutation), et trois fois cela dans le pire cas (tout doit être permuté)... donc la complexité algorithmique de ces algorithmes est , ce qui en fait un algorithme dispendieux.

Tri par insertion

Un autre tri simpliste, un peu meilleur que le tri à bulles mais sans plus, est le tri par insertion. Plutôt que de parcourir de la main droite vers la droite, celui-ci va vers la gauche, et tend à faire un peu moins de permutations que son prédécesseur.

Le code suit.

using System;
public class Program
{
   static void Permuter(ref int a, ref int b)
   {
      int temp = a;
      a = b;
      b = temp;
   }
   static void TriInsertion(int[] vals)
   {
      for (int i = 1; i < vals.Length; ++i)
         for (int j = i; j > 0 && vals[j] < vals[j-1]; --j)
            Permuter(ref vals[j - 1], ref vals[j]);
   }
   static void Afficher(int []tab)
   {
      for(int i = 0; i != tab.Length; ++i)
         Console.Write($"{tab[i]} ");
      if (EstTrié(tab))
         Console.WriteLine("... il est donc trié");
      else
         Console.WriteLine("... il n'est donc pas trié");
   }
   static bool EstTrié(int [] tab)
   {
      for(int i = 1; i < tab.Length; ++i)
         if (tab[i] < tab[i-1])
            return false;
      return true;
   }
   static void TestTri(int [] tab)
   {
      Console.Write("Avant : ");
      Afficher(tab);
      TriInsertion(tab);
      Console.Write("Après : ");
      Afficher(tab);
   }
   public static void Main()
   {
      TestTri(new int[]{}); // tableau vide
      TestTri(new int[]{ 1,2,3,4,5 }); // tableau déjà trié
      TestTri(new int[]{ 5,1,4,2,3 }); // tableau en désordre, taille impaire
      TestTri(new int[]{ 5,1,6,4,2,3 }); // tableau en désordre, taille paire
   }
}

Des algorithmes comme les deux précédents, bien qu'opérationnels, ne sont pas utilisables en pratique sur de grandes séquences d'éléments (leur complexité algorithmique est déraisonnable).

Tri fusion

Un tri fusion, bien que plus complexe que les prédécents, est aussi beaucoup plus efficace (même si l'implémentation ci-dessous est naïve et perfectible). En gros :

Le code suit.

using System;
public class Program
{
   static void Permuter(ref int a, ref int b)
   {
      int temp = a;
      a = b;
      b = temp;
   }
   static void TriBulles(int[] vals, int min, int max)
   {
      for (int i = min; i < max - 1; ++i)
         for (int j = i + 1; j < max; ++j)
            if (vals[j] < vals[i])
               Permuter(ref vals[i], ref vals[j]);
   }
   const int SEUIL_FUSION = 10; // arbitraire
   static void Fusionner(int[] vals, int min, int milieu, int max)
   {
      int i = min, j = milieu;
      // ceci est lâche; il y a une solution qui n'alloue pas de mémoire
      // mais elle est plus compliquée
      int[] temp = new int[Distance(min, max)];
      int n = 0;
      while (i != milieu && j != max)
      {
         if (vals[i] < vals[j])
            temp[n] = vals[i++];
         else
            temp[n] = vals[j++];
         ++n;
      }
      // ici, soit i == milieu, soit j == max donc une seule des
      // deux boucles va être utilisée
      while (i != milieu)
         temp[n++] = vals[i++];
      while (j != max)
         temp[n++] = vals[j++];
      // on recopie temp dans vals entre min et max
      for (int k = 0; k != temp.Length; ++k)
         vals[k + min] = temp[k];
   }
   static void TriFusion(int[] vals, int min, int max)
   {
      if (vals.Length <= SEUIL_FUSION)
         TriBulles(vals, min, max);
      else
      {
         int milieu = PointMilieu(min, max);
         TriFusion(vals, min, milieu);
         TriFusion(vals, milieu, max);
         Fusionner(vals, min, milieu, max);
      }
   }
   static int Distance(int min, int max) =>
      Math.Abs(max - min); // naïf : incorrect si signes différents
   static int PointMilieu(int min, int max) =>
      (min + max) / 2; // naïf : incorrect si min + max >= int.MaxValue
                       // (entre autres bogues)
   static void TriFusion(int[] vals) => TriFusion(vals, 0, vals.Length);
   static void Afficher(int []tab)
   {
      for(int i = 0; i != tab.Length; ++i)
         Console.Write($"{tab[i]} ");
      if (EstTrié(tab))
         Console.WriteLine("... il est donc trié");
      else
         Console.WriteLine("... il n'est donc pas trié");
   }
   static bool EstTrié(int [] tab)
   {
      for(int i = 1; i < tab.Length; ++i)
         if (tab[i] < tab[i-1])
            return false;
      return true;
   }
   static void TestTri(int [] tab)
   {
      Console.Write("Avant : ");
      Afficher(tab);
      TriFusion(tab);
      Console.Write("Après : ");
      Afficher(tab);
   }
   public static void Main()
   {
      TestTri(new int[]{}); // tableau vide
      TestTri(new int[]{ 1,2,3,4,5 }); // tableau déjà trié
      TestTri(new int[]{ 5,1,4,2,3 }); // tableau en désordre, taille impaire
      TestTri(new int[]{ 5,1,6,4,2,3 }); // tableau en désordre, taille paire
   }
}

Cette implémentation est inefficace (elle alloue de la mémoire pour la fusion), et plus risquée qu'il n'y paraît (les fonctions Distance et PointMilieu sont trop naïves pour usage commercial; elles ont des bogues qui transparaissent quand on opère sur des séquences de grande taille).

En retour, sa complexité algorithmique est , ce qui est nettement meilleur que . Imaginez seulement  : avec , on parle de opérations environ, alors qu'avec , on parle plutôt de opérations... C'est majeur! Et éléments à trier, c'est presque rien...

Utiliser Array.Sort()

La plupart des langages de programmation offrent des mécanismes (typiquement des fonctions ou des bibliothèques) pour trier des séquences de valeurs.

Certains de ces mécanismes sont très génériques, comme std::sort() de C++ qui permet de trier plusieurs types de séquences, alors que d'autres le sont un peu moins comme Array.Sort de C# qui donne un contrôle sur le critère d'ordonnancement des valeurs, mais qui se limite aux tableaux.

Avec Array.Sort, il suffit de passer le tableau à trier à la fonction pour avoir un tri en ordre croissant de valeurs... dans la mesure où la fonction sait comment comparer ces valeurs. Il est aussi possible de passer un comparateur en paramètre à la fonction, ce qui est utile si (a) on souhaite un placer les valeurs dans un ordre autre que l'ordre croissant, ou (b) quand la fonction ne sait pas comment ordonnancer les valeurs que nous lui offrons.

Ce qui suit trie les entiers d'un tableau en ordre croissant :

using System;
public class Program
{
   static void Afficher(int []tab)
   {
      for(int i = 0; i != tab.Length; ++i)
         Console.Write($"{tab[i]} ");
      if (EstTrié(tab))
         Console.WriteLine("... il est donc trié");
      else
         Console.WriteLine("... il n'est donc pas trié");
   }
   static bool EstTrié(int [] tab)
   {
      for(int i = 1; i < tab.Length; ++i)
         if (tab[i] < tab[i-1])
            return false;
      return true;
   }
   static void TestTri(int [] tab)
   {
      Console.Write("Avant : ");
      Afficher(tab);
      Array.Sort(tab);
      Console.Write("Après : ");
      Afficher(tab);
   }
   public static void Main()
   {
      TestTri(new int[]{}); // tableau vide
      TestTri(new int[]{ 1,2,3,4,5 }); // tableau déjà trié
      TestTri(new int[]{ 5,1,4,2,3 }); // tableau en désordre, taille impaire
      TestTri(new int[]{ 5,1,6,4,2,3 }); // tableau en désordre, taille paire
   }
}

C'est simple et efficace.

Trier avec comparateurs

Un comparateur au sens de la méthode Array.Sort est une fonction prenant deux valeurs du type à trier, et retournant un entier :

Cela signifie que, pour trier un tableau tab en ordre croissant, ceci :

static void Trier(int [] tab)
{
   Array.Sort(tab);
}

... est équivalent à ceci :

static int Comparateur(int a, int b) => a - b;
static void Trier(int [] tab)
{
   Array.Sort(tab, Comparateur);
}

... ou encore à cela (si vous êtes familières ou familiers avec les expressions λ) :

static void Trier(int [] tab)
{
   Array.Sort(tab, (a,b) => a - b);
}

Notez au passage que, pour les types qui implémentent l'interface IComparable (ce qui inclut les int), la méthode CompareTo fait un travail approprié pour les besoins de la méthode Array.Sort :

static int Comparateur(int a, int b) => a.CompareTo(b);
static void Trier(int [] tab)
{
   Array.Sort(tab, Comparateur);
}

À titre d'exemple, ce qui suit trie des entiers en ordre décroissant :

using System;
public class Program
{
   static void Afficher(int[] tab)
   {
      for (int i = 0; i != tab.Length; ++i)
         Console.Write($"{tab[i]} ");
      Console.WriteLine();
   }
   static int PlusGrand(int a, int b) => b.CompareTo(a); // négatif si b < a, 0 si b == a, positif si a < b
   static void TestTri(int[] tab)
   {
      Console.Write("Avant : ");
      Afficher(tab);
      Array.Sort(tab, PlusGrand);
      Console.Write("Après : ");
      Afficher(tab);
   }
   public static void Main()
   {
      TestTri(new int[]{}); // tableau vide
      TestTri(new int[]{ 1,2,3,4,5 }); // tableau déjà trié
      TestTri(new int[]{ 5,1,4,2,3 }); // tableau en désordre, taille impaire
      TestTri(new int[]{ 5,1,6,4,2,3 }); // tableau en désordre, taille paire
   }
}

Enfin, ce qui suit trie des instances de Personne en ordre lexicographique :

using System;
public class Program
{
   class Personne
   {
      public string Prénom { get; }
      public string Nom { get; }
      public Personne(string nom, string prénom)
      {
         Nom = nom;
         Prénom = prénom;
      }
   }
   static void Afficher(Personne [] population)
   {
      for (int i = 0; i != population.Length; ++i)
         Console.Write($"{population[i].Nom}, {population[i].Prénom} ; ");
      Console.WriteLine();
   }
   static int OrdreLexicographique(Personne p0, Personne p1)
   {
      int résultat = string.Compare(p0.Nom, p1.Nom);
      if (résultat == 0)
         résultat = string.Compare(p0.Prénom, p1.Prénom);
      return résultat;
   }
   static void TestTri(int[] tab)
   {
      Console.Write("Avant : ");
      Afficher(tab);
      Array.Sort(tab, OrdreLexicographique);
      Console.Write("Après : ");
      Afficher(tab);
   }
   public static void Main()
   {
      TestTri(new Personne[]
      {
         new Personne("Tremblay", "Bill"),
         new Personne("Nguyen", "Kim"),
         new Personne("Popovic", "Peter"),
         new Personne("Tremblay", "Anne"),
         new Personne("Nguyen", "Zénon")
      });
   }
}

Voilà.

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !