Fonction de comparaison Qsort

Je suis un débutant en C et j’essaie de comprendre la fonction de comparaison nécessaire pour la fonction qsort.

Première partie: syntaxe

Une simple utilisation suggérée est la suivante (j’ai inclus du code main () pour imprimer également les résultats):

#include  #include  int values[] = { 40, 10, 100, 90, 20, 25, 12, 13, 10, 40 }; int compare(const void *a, const void *b) { const int *ia = (const int *)a; // casting pointer types const int *ib = (const int *)b; return *ia - *ib; } int main() { int n; for (n=0; n<10; n++) { printf("%d ",values[n]); } printf("\n"); qsort(values, 10, sizeof(int), compare); for (n=0; n<10; n++) { printf("%d ",values[n]); } printf("\n"); system("pause"); return 0; } 

Je ne comprends pas pourquoi vous avez besoin de toutes les choses supplémentaires dans la fonction de comparaison, je l’ai donc simplifiée:

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

Cela fonctionne toujours et produit les mêmes résultats. Quelqu’un peut-il m’expliquer ce que j’ai supprimé et pourquoi cela fonctionne toujours?

Deuxième partie: Pourquoi des pointeurs?

De plus, dois-je vraiment utiliser des pointeurs? Pourquoi ne puis-je pas simplement comparer “a” et “b” directement comme si (cela ne fonctionne pas):

 int compare (int a, int b) { return ab; } 

Pour une raison quelconque, avec un tableau multidimensionnel, j’ai été capable de ne PAS utiliser de pointeurs et pour une raison quelconque, cela a fonctionné! Que se passe-t-il? (Exemple de code de sorting d’un tableau multidimensionnel par le 2ème élément de chaque sous-tableau):

 #include  #include  int values[7][3] = { {40,55}, {10,52}, {100,8}, {90,90}, {20,91}, {25,24} }; int compare(int a[2], int b[2]) { return a[1] - b[1]; } int main() { int n; for (n=0; n<6; n++) { printf("%d,",values[n][0]); printf("%d ",values[n][1]); } printf("\n"); qsort(values, 6, sizeof(int)*3, compare); for (n=0; n<6; n++) { printf("%d,",values[n][0]); printf("%d ",values[n][1]); } printf("\n"); system("pause"); return 0; } 

Je suis vraiment heureux que le sorting multidimensionnel de tableaux fonctionne, car c’est mon objective final de toute façon, mais je n’ai aucune idée de la façon dont j’ai réussi à le faire fonctionner (autre que de la chance stupide et du découpage du code), donc j’aimerais vraiment une explication comme pourquoi certains exemples que j’ai fournis fonctionnent et pourquoi d’autres ne le font pas!

Cela fonctionne toujours et produit les mêmes résultats. Quelqu’un peut-il m’expliquer ce que j’ai supprimé et pourquoi cela fonctionne toujours?

Vous appelez un comportement non défini en C. Voir C99, 6.3.2.3 Pointeurs / 8:

Un pointeur sur une fonction d’un type peut être converti en un pointeur sur une fonction d’un autre type et inversement; le résultat doit être égal au pointeur d’origine. Si un pointeur converti est utilisé pour appeler une fonction dont le type n’est pas compatible avec le type pointé, le comportement est indéfini.

En C ++, ce programme est carrément mal formé: http://ideone.com/9zRYSj

Cela fonctionne toujours “parce que la fonction de compare attend deux pointeurs; et sur votre plate-forme particulière, sizeof(void*) est identique à sizeof(int*) . Vous devez donc appeler un pointeur de fonction de type int(void *, void *) qui contient en fait un pointeur sur une fonction de type int(int *, int *) est en réalité identique au type de pointeur jeté sur votre plate-forme particulière à ce moment précis.

De plus, dois-je vraiment utiliser des pointeurs? Pourquoi ne puis-je pas simplement comparer “a” et “b” directement comme si (cela ne fonctionne pas):

Parce que qsort prend une fonction de comparaison générale pour deux types quelconques; pas seulement int . Donc, il ne sait pas quel type auquel le pointeur est déréférencé.

Pour une raison quelconque, avec un tableau multidimensionnel, j’ai été capable de ne PAS utiliser de pointeurs et pour une raison quelconque, cela a fonctionné! que se passe-t-il!

En effet, les prototypes suivants sont les mêmes:

  1. int foo(int *a, int *b);
  2. int foo(int a[], int b[])

C’est-à-dire qu’un tableau se décompose en un pointeur lorsqu’il est transmis à une fonction. Spécifier explicitement la longueur du tableau comme vous l’avez fait:

 int foo(int a[2], int b[2]) 

oblige le compilateur à faire en sorte que sizeof et d’autres bits de temps de compilation traitent l’élément comme un tableau à deux éléments; mais la fonction accepte toujours une paire de pointeurs lorsqu’elle atteint le niveau de la machine.

Dans tous les cas, le fait de passer une fonction de comparaison qui ne prend pas une paire de void * s entraîne un comportement indéfini. Un résultat valide de “comportement indéfini” est “cela semble juste fonctionner”. Un autre résultat valide serait “cela fonctionne les mardis” ou “il formate le disque dur”. Ne comptez pas sur ce comportement.

Je ne comprends pas pourquoi vous avez besoin de toutes les fonctionnalités supplémentaires de la fonction de comparaison, aussi je l’ai simplifiée

Que vous const qualificatif const est à vous. En effet, vous ne devez pas modifier les valeurs dans le comparateur. Mais il est possible de rejeter le const et de rompre la promesse que vous faites au compilateur.


qsort attend un pointeur de fonction qui prend deux const void * tant que parameters. C’est pourquoi les pointeurs sont transmis pour la fonction comparateur:

  void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); 

Donc passer a et b conduirait à interpréter les valeurs comme des indicateurs, ce qui est évidemment faux.


Cela fonctionne sans passer de pointeur pour les tableaux multidimensionnels car, lorsque vous passez des tableaux, ils se décomposent en pointeurs. Donc, le comparateur suivant que vous avez est ok.

 int compare (int a[2], int b[2]) { return a[1] - b[1]; } 

La réponse est très simple: dans le manuel de qsort http://pubs.opengroup.org/onlinepubs/009695399/functions/qsort.html, le prototype du pointeur de fonction est le suivant:

 int comp(const void *a, const void *b) 

Le typedef associé à ce prototype peut être déclaré de cette façon

 typedef int (*comp_qsort_funct_t) ( const void *, const void * ) 

comp_qsort_funct_t est le type du pointeur de la fonction

Le prototype de la fonction de comparaison de qsort utilise la variable const car il s’agit d’une bonne pratique / conception, car les données ne seront pas modifiées.

L’utilisation d’un prototype différent peut entraîner des résultats inattendus selon le compilateur / la plate-forme. Ou tout simplement ne pas comstackr, exemple fourni dans le commentaire: http://ideone.com/9zRYSj

Donc, vous ne devez pas utiliser un prototype différent.

Je voudrais confirmer les observations de Dlinet qui a posé la question initiale.

Le compilateur C acceptera en effet toutes les formes de la fonction de comparaison, même sans const, et même en utilisant int * au lieu de void *. Cependant, mon compilateur C ++ rejette les variations et n’accepte que la forme const void *.

Le compilateur C accepte même la forme int sans utiliser de pointeur. J’ai vérifié et constaté que la forme int de la fonction de comparaison recevait des valeurs de pointeur , pas les enttes du tableau. Et le résultat est que le tableau n’est pas sortingé mais rest dans le même ordre. Et je pense que tout cela correspond à ce que vous attendez.

Ainsi, il semblerait que vous puissiez utiliser int * au lieu de void * dans la définition de la fonction, sans avoir à transtyper la fonction.

La question de savoir si c’est une bonne pratique de programmation est discutable, certains programmeurs disant oui et d’autres non. Il me semble que la programmation soit bonne ou pas, la réduction de l’encombrement serait un point en faveur de l’utilisation de int * au lieu de void *. Mais alors, un compilateur C ++ ne vous laisse pas faire cela.