Il ne devrait pas être nécessaire de souligner que la fonction de comparaison dans le PO est incorrecte, et que son utilisation est un comportement non défini. Néanmoins, il est intéressant de se demander comment cela pourrait fonctionner.
Bien que l'interface avec qsort exige une fonction de comparaison qui renvoie un entier, en prévoyant trois valeurs de retour possibles, rien n'oblige l'utilisateur de l qsort la mise en œuvre pour utiliser toutes ces informations. Elle pourrait toujours effectuer la même branche simple à deux voies. Cela serait similaire à la méthode Bibliothèque standard C++ sort fonction dont le comparateur renvoie un booléen, vrai si le premier argument est strictement inférieur au second.
Bien entendu, la fonction comparateur de votre élève n'indiquera jamais que le premier argument est strictement inférieur au second, ce qui poserait des problèmes pour une implémentation dans laquelle les tests ressemblent à quelque chose du genre :
if (*cmp(p, q) < 0) ...
Cependant, si le comparateur est toujours appelé comme :
if (*cmp(p, q) > 0) ...
(ou, de manière équivalente, <= ), alors le comparateur de votre élève fonctionnera sans problème.
Comme la glibc est open source, il est facile de vérifier, une fois que nous avons trouvé la fonction de tri correcte. Mais tout n'est pas tout à fait comme il semble. Il y a un fichier source appelé qsort.c (dans le stdlib ), qui implémente l'algorithme quicksort ( pas l'algorithme d'introsort utilisé par les plus modernes std::sort ), et dans ce fichier nous pouvons voir une utilisation cohérente de strict less than. Par exemple, dans le fichier boucle interne principale :
while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
left_ptr += size;
while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
right_ptr -= size;
(Il existe de nombreuses autres comparaisons dans la fonction, mais elles ont toutes la même forme).
Cela ne devrait donc pas fonctionner du tout avec le comparateur de votre élève. Cependant, il s'avère que ce n'est pas la fonction habituellement appelée par qsort . qsort est en fait défini dans le fichier msort.c qui implémente un tri par fusion. Et la fonction de tri par fusion effectue des tests de type "moins que ou égal à". Par exemple :
if ((*cmp) (b1, b2, arg) <= 0)
L'implémentation du tri par fusion n'est pas in-place, ce qui serait plus lent ; elle nécessite une mémoire temporaire. Et cela pourrait être un problème, car qsort devrait fonctionner même si aucune mémoire temporaire n'est disponible. Ainsi, l'implémentation réelle de qsort commence par essayer de savoir si la mémoire physique disponible est suffisante. (Il veut de la mémoire physique, pas de l'espace de swap, afin d'éviter le swapping. Rappelez-vous également que Linux procède à une allocation optimiste, de sorte que le fait que malloc réussisse n'implique pas nécessairement que les adresses de mémoire virtuelle allouées soient réellement utilisables). Ici, il a calculé l'espace temporaire nécessaire (en milliers d'euros). size ) et utilisé sysconf pour demander combien de mémoire physique possède l'hôte. (Il divise cette valeur par quatre afin de ne pas monopoliser toute la mémoire physique).
/* If the memory requirements are too high don't allocate memory. */
if (size / pagesize > (size_t) phys_pages)
{
_quicksort (b, n, s, cmp, arg);
return;
}
Donc, si le tri par fusion nécessite trop de mémoire, il s'en remet à _quicksort qui est précisément la fonction que j'ai citée précédemment et qui se trouve dans qsort.c .
En résumé :
-
La fonction de comparateur défectueux fonctionnera avec la glibc qsort à condition que le tableau à trier ne soit pas trop grand.
-
Si le tableau est trop grand, le tri échouera.
En revanche, le système BSD qsort utilise les trois valeurs de retour des comparateurs. Dans son boucle intérieure nous voyons :
while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
if (cmp_result == 0) {
swap_cnt = 1;
swap(pa, pb);
pa += es;
}
pb += es;
}
while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
if (cmp_result == 0) {
swap_cnt = 1;
swap(pc, pd);
pd -= es;
}
pc -= es;
}
Il y a également des appels au comparateur pour trouver le pivot ; ce sont tous les < ils produiront donc également une mauvaise réponse. Cependant, tout n'est pas perdu ; pour les très petits vecteurs (moins de sept éléments), il utilise le tri par insertion à la place, et la boucle de tri par insertion utilise une comparaison stricte de type plus grand que.
