Fonctions de comparaison : une erreur fréquente

Contexte

Premièrement, qu’est-ce que j’entends par « fonction de comparaison » ?
Je parle des fonctions qui prennent deux arguments en entrée et qui renvoie :

• un nombre positif si le premier argument est strictement supérieur au second.
• 0 si les deux arguments sont égaux.
• un nombre négatif si le premier argument est strictement inférieur au second.

Ce genre de fonction est utilisée pour ordonner des éléments (ordre total), et elles sont donc naturellement utilisée par certaines fonctions de tri telles que qsort.

Maintenant, pourquoi est-ce que je parle d’une erreur répandue ?
Et bien parce qu’en tapant « qsort » ou « qsort example » dans un moteur de recherche, je tombe sur ça (il y a aussi des versions correctes, je vous rassure) :

• cplusplus.com
• bien-programmer.fr
• tutorialspoint.com
• anyexample.com

Problème

Alors, quel est le problème ?
Prenons l’exemple donné sur le site cplusplus.com :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* qsort example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

Si on teste cet exemple, on obtient bien le résultat attendu :

10 20 25 40 90 100

Bien, et si maintenant on utilise¹ :

int values[] = { 40, INT_MIN, 100, INT_MAX, 20, INT_MIN + 42 };

Alors là, rien ne va plus ! En sortie on obtient :

40 100 2147483647 -2147483648 -2147483606 20

Ce qui ne correspond pas du tout à un tableau trié par ordre croissant.

Explication

Le souci vient de la fonction de comparaison :

1
2
3
4

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

L’idée derrière cette fonction est que comme on doit renvoyer un nombre positif si a > b, négatif is a > b et 0 si a = b alors autant renvoyer la différence.

En théorie, ça fonctionne. En pratique, les nombres représentables dans un int sont bornés et il y a donc risque d’overflow lorsque l’on approche les valeurs limites. Et en effet, l’opération a - b peut produire un résultat non représentable dans un int.

À toutes fins utiles, je rappelle que les overflow d’entiers signés en C sont un comportement non-défini. Cela vient en partie du fait que le standard du C n’impose rien sur la représentation des entiers signés (signe et magnitude, complément à un ou complément à deux) et ne veut donc pas dicter le comportement attendu pour ce genre de situation.

Solution

La solution est très simple. Étant donné que l’on souhaite faire une fonction de comparaison il suffit d’utiliser les opérateurs de comparaison afin d’éviter tout problème d’overflow :

1
2
3
4
5
6
7
8
9
10
11
12

int compare (const void * a, const void * b)
{
    const int* left = a;
    const int* right = b;

    if (*left > *right)
        return 1;
    else if (*left < *right)
        return -1;
    else
        return 0;
}

Et pour ceux qui trouvent l’alternative précédente trop verbeuse, il est toujours possible l’utiliser l’idiome suivant :

1
2
3
4
5
6

int compare (const void * a, const void * b)
{
    const int* left = a;
    const int* right = b;
    return (*left > *right) - (*left < *right);
}

Cette version se base sur le fait que les opérateurs > et < renvoie 0 ou 1, ce qui est garanti par le standard (Cf. ISO/IEC 9899:TC3, 6.5.8 Relational operators §6, page 86) :

[…]
Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.)
The result has type int.
[…]

Cette version est donc absolument portable et devrait même fonctionner sur un DS9K :P