Par l'équipe Codermind. |
Question
«Je sais trier des entiers ou des chaînes de caractères avec la fonction qsort()
mais je bloque sur le problème suivant. Imaginons que je veuille trier selon plusieurs critères. Par exemple j'ai un nom et un âge. Je veux d'abord trier par âge puis par nom à l'intérieur d'un même âge. Est-ce que si je trie les entrées par âge et ensuite je trie par nom je vais perdre l'ordre par âge, non ? Et si je rajoute un troisième critère ?»
Réponse
Ce problème est assez fréquent chez les débutants. En effet, le tri multi-critère est facile à faire dans Excel mais comment faire pour le programmer ?
La chose essentielle à comprendre c'est que tri multicritère == tri à un seul critère. Et oui ! Si l'on sait faire l'un on sait faire l'autre.
struct foo { int a; int b; int c; };
Imaginons qu'on ait un tableau de qsort, introduisons la fonction compare ci dessous :
int compare (void *foo1, void * foo2) {
foo *truefoo1 = (foo *)foo1;
foo *truefoo2 = (foo *)foo2;
if (truefoo1->a - truefoo2->a != 0)
return truefoo1->a - truefoo2->a;
else if (truefoo1->b - truefoo2->b != 0)
return truefoo1->b - truefoo2->b;
else
return truefoo1->c - truefoo2->c;
}et ensuite il suffit d'appeler qsort sur notre tableau de valeur:
qsort(arrayoffoo, n, sizeof(foo), compare);
Et notre tableau sera trié.
Voilà : l'algorithme ne change pas, seule la fonction compare doit maintenant prendre en compte trois critères pour définir l'ordre des éléments entre eux.
Digression: une autre manière de trier des objets sur plusieurs critères a été mis à profit par les machines à trier des premiers recensements. Il s'agit de trier les objets dans des seaux (buckets) en plusieurs étapes et de maintenir l'ordre relatif des objets à l'intérieur d'un même seau. Si l'on trie selon prénom, alors on triera selon nom en faisant en sorte que pour un même nom l'ordre des prénoms soit maintenu. En bout de chaine on aura donc une liste triée correctement selon les deux critères. Si c'est particulièrement adapté au tri mécanique, cela a aussi donné naissance à un tri super rapide des entiers sur ordinateur : le tri radix.