qsort en C : comparateur sans overflow
Comment écrire le comparateur de qsort en C : cast des void *, signe de retour, piège de a - b et tri fiable de INT_MIN à INT_MAX.
Tu passes qsort à un tableau d'int, puis il te demande une fonction avec deux const void *. Le cast a l'air gratuit, beaucoup de tutos répondent par return a - b, et le tri semble marcher. Jusqu'au jour où ton tableau contient INT_MIN et INT_MAX.
En bref
La fonction de comparaison de qsort reçoit les adresses de deux éléments. Pour des int, convertis chaque adresse en const int *, lis la valeur, puis renvoie un nombre négatif, zéro ou positif selon l'ordre. Écris return (left > right) - (left < right);, pas left - right : cette soustraction peut déborder pour deux entiers valides, ce qui est un comportement indéfini en C.
Que reçoit vraiment le comparateur de qsort ?
qsort ne connaît pas le type des éléments. Il connaît l'adresse du tableau, le nombre d'éléments, leur taille et une fonction à appeler. Les deux arguments de cette fonction sont donc des adresses, pas les deux int eux-mêmes.
#include <stdio.h>#include <stdlib.h>
static int compare_ints(const void *first, const void *second){ int left = *(const int *)first; int right = *(const int *)second;
return (left > right) - (left < right);}
int main(void){ int values[] = {7, -4, 0, 42}; size_t count = sizeof values / sizeof values[0];
qsort(values, count, sizeof values[0], compare_ints); for (size_t i = 0; i < count; i++) printf("%d%c", values[i], i + 1 == count ? '\\n' : ' '); return 0;}$ gcc -Wall -Wextra -Werror -g tri.c -o tri$ ./tri-4 0 7 42Le cast dit au compilateur quel type se trouve à cette adresse. Le * lit ensuite cet int. Après cela, qsort ne regarde que le signe du résultat : négatif quand left doit passer avant right, positif dans l'autre sens, zéro si les deux sont égaux.
- qsortdeux adresses d'éléments
- const void *first et second
- intleft et right
- signe-1, 0 ou 1
Le type de cast change avec le tableau. Pour struct score, utilise const struct score *. Pour un tableau de chaînes, les éléments sont des char *, donc les arguments sont des pointeurs vers ces pointeurs, const char *const *.
Pourquoi return left - right peut casser le tri ?
Parce qu'une différence entre deux int peut être hors de l'intervalle d'un int. INT_MIN - INT_MAX n'est pas représentable. La norme C laisse alors le comportement indéfini : aucun résultat de comparaison n'est garanti.
#include <limits.h>#include <stdio.h>
static int compare_by_subtraction(const void *first, const void *second){ int left = *(const int *)first; int right = *(const int *)second;
return left - right;}
int main(void){ int low = INT_MIN; int high = INT_MAX;
printf("%d\\n", compare_by_subtraction(&low, &high)); return 0;}$ gcc -Wall -Wextra -Werror -fsanitize=undefined -g soustraction.c -o soustraction$ ./soustractionsoustraction.c:9:17: runtime error: signed integer overflow: -2147483648 - 2147483647 cannot be represented in type 'int'1Le 1 final est une valeur observée sur cet environnement, pas un ordre fiable. Le sanitizer a trouvé l'erreur avant que tu puisses faire confiance au tri.
La version par comparaisons ne soustrait jamais les données. Chaque comparaison donne 0 ou 1, et leur différence est forcément dans {-1, 0, 1}.
#include <limits.h>#include <stdio.h>#include <stdlib.h>
static int compare_ints(const void *first, const void *second){ int left = *(const int *)first; int right = *(const int *)second;
return (left > right) - (left < right);}
int main(void){ int values[] = {INT_MAX, 0, INT_MIN};
qsort(values, 3, sizeof values[0], compare_ints); printf("%d %d %d\\n", values[0], values[1], values[2]); return 0;}$ gcc -Wall -Wextra -Werror -fsanitize=undefined -g bornes.c -o bornes$ ./bornes-2147483648 0 2147483647
qsort
L'exercice qsort te fait réécrire le mécanisme de tri avec void *, une taille d'élément et un comparateur. Les tests passent par des char, des long et des structures : si tu supposes que tout est un int, ils te le montreront tout de suite.
Comment trier des structures et des chaînes ?
Une structure se compare par le champ qui décide l'ordre. Garde la même forme de comparaison pour un champ int, puis ajoute une règle de départage si l'ordre doit rester prévisible quand deux scores sont égaux.
#include <stdio.h>#include <stdlib.h>#include <string.h>
struct score { const char *name; int points;};
static int compare_scores(const void *first, const void *second){ const struct score *left = first; const struct score *right = second; int order = (left->points > right->points) - (left->points < right->points);
if (order != 0) return order; return strcmp(left->name, right->name);}
int main(void){ struct score values[] = {{"Lina", 12}, {"Adam", 12}, {"Maya", 7}}; size_t count = sizeof values / sizeof values[0];
qsort(values, count, sizeof values[0], compare_scores); for (size_t i = 0; i < count; i++) printf("%s: %d\\n", values[i].name, values[i].points); return 0;}$ gcc -Wall -Wextra -Werror -g scores.c -o scores$ ./scoresMaya: 7Adam: 12Lina: 12Pour trier des chaînes, le tableau contient des pointeurs vers char. Le comparateur reçoit donc l'adresse d'un élément qui est déjà un pointeur : il faut déréférencer une fois pour atteindre le char *, puis appeler strcmp.
#include <stdio.h>#include <stdlib.h>#include <string.h>
static int compare_words(const void *first, const void *second){ const char *const *left = first; const char *const *right = second;
return strcmp(*left, *right);}
int main(void){ const char *words[] = {"zebra", "ant", "mango"}; size_t count = sizeof words / sizeof words[0];
qsort(words, count, sizeof words[0], compare_words); for (size_t i = 0; i < count; i++) puts(words[i]); return 0;}$ gcc -Wall -Wextra -Werror -g mots.c -o mots$ ./motsantmangozebraqsort ne garantit pas l'ordre relatif de deux éléments que ton comparateur considère égaux. Si cet ordre compte, ajoute un départage, comme le nom dans l'exemple, ou garde l'index d'origine avec chaque élément.
Pour remettre les types en place, lis Tableau ou pointeur en C. Pour la mécanique des pointeurs de fonction, Pointeurs en C détaille leur déclaration. Le débordement signé appartient à la même famille que les exemples de comportement indéfini.
Questions fréquentes
Le comparateur doit-il renvoyer exactement -1, 0 ou 1 ?
Non. qsort demande seulement un résultat négatif, nul ou positif. La formule avec deux comparaisons renvoie ces trois valeurs et évite l'overflow.
Pourquoi return left - right semble marcher ?
Parce que des valeurs assez proches ne font pas déborder la soustraction. Le cas limite reste un programme C incorrect, même si ton processeur produit souvent un nombre qui a l'air plausible.
qsort garde-t-il l'ordre de deux éléments égaux ?
Non. Leur ordre final est non spécifié. Ajoute une seconde comparaison si tu veux un ordre déterminé.
Faut-il écrire sizeof(int) dans l'appel à qsort ?
sizeof values[0] est préférable : si le type du tableau change, la taille suit sans modification. Le même principe évite de recopier une taille dans Tableau ou pointeur en C.
Sources