Quelques raccourcis :
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).
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 (https://dotnetfiddle.net/8mZlJQ) :
using System;
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
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);
}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.
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 (https://dotnetfiddle.net/SjbWXB) :
using System;
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
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);
}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).
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 (https://dotnetfiddle.net/tG5GIE) :
using System;
using static AlgosTri;
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
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 void TestTri(int [] tab)
{
Console.Write("Avant : ");
Afficher(tab);
TriFusion(tab);
Console.Write("Après : ");
Afficher(tab);
}
static class AlgosTri
{
public static void TriFusion(int[] vals) => TriFusion(vals, 0, vals.Length);
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);
}
}
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];
}
public static void Permuter(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
public 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]);
}
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)
public static bool EstTrié(int [] tab)
{
for(int i = 1; i < tab.Length; ++i)
if (tab[i] < tab[i-1])
return false;
return true;
}
}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...
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 (https://dotnetfiddle.net/GKB8Sa) :
using System;
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
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);
}C'est simple et efficace.
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 (https://dotnetfiddle.net/TjEhbV) :
using System;
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
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);
}Enfin, ce qui suit trie des instances de Personne en ordre lexicographique (https://dotnetfiddle.net/IbsUTd) :
using System;
TestTri(new Personne[]
{
new Personne("Tremblay", "Bill"),
new Personne("Nguyen", "Kim"),
new Personne("Popovic", "Peter"),
new Personne("Tremblay", "Anne"),
new Personne("Nguyen", "Zénon")
});
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(Personne[] tab)
{
Console.Write("Avant : ");
Afficher(tab);
Array.Sort(tab, OrdreLexicographique);
Console.Write("Après : ");
Afficher(tab);
}
class Personne
{
public string Prénom { get; }
public string Nom { get; }
public Personne(string nom, string prénom)
{
Nom = nom;
Prénom = prénom;
}
}Voilà.
Quelques liens pour enrichir le propos.
