Tri multicritère

(drop the hyphen! comme dirait D. Knuth)

Une question qui semble souvent bloquer sans raison les débutants en programmation est le tri sur plusieurs critères.

En général la première des choses que l’on apprend en cours d’algorithmique est la fonction qsort. Et en général on trie des entiers n selon une simple fonction compare qui retourne qui de n1 ou n2 est le plus grand.

Maintenant là où ça se complique c’est si l’on introduit plusieurs critères de tri comme le nom, puis le prénom puis la date de naissance et le lieu de naissance. C’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 struct foo que l’on désire trier selon a puis selon b puis selon c sans devoir réécrire la fonction 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.