Le tri rapide est-il si rapide?

aussi le plus souple possible.
Pour qu’une routine de tri sache où placer chaque élément d’une matrice, il lui faut comparer les éléments entre eux. Effectuée en boucle, cette comparaison détermine l’ordre final obtenu en fin de tri. Par conséquent, il faut laisser le programmeur contrôler les modalités de comparaison des éléments entre eux, pour lui offrir le maximum de souplesse.
Voyons comment QSORT obtient sa souplesse. Vous écrivez votre propre sous-procédure qui compare deux éléments de la matrice, et QSORT appelle la sous-procédure avant d’effectuer une comparaison. De sorte que vous pouvez faire pratiquement ce que vous voulez ! En effet, comme vous écrivez la routine de comparaison, QSORT n’a pas à comprendre le format des données qu’elle trie. Vous pouvez trier sur une matrice ordinaire ou sur une matrice de structure de données, ou encore sur une structure de données à occurrences multiples (MODS, multiple-occurrence data structure) avec facilité. Et aussi effectuer des calculs spécialisés. Par exemple, vous pourriez mettre en capitales les mots avant de les comparer, afin que le tri soit insensible à la casse. C’est parfaitement possible puisque vous êtes le seul à écrire le code de comparaison. Pour plus d’exemples de la souplesse de QSORT, v o i r « T h e QSORT Function » (www.itpro.fr Club abonnés), dans lequel j’ai démontré l’utilisation de QSORT.

Pour cet exemple, j’ai gardé les routines de comparaison courtes et nettes afin que leurs résultats soient comparables à ceux que vous obtiendriez par les autres méthodes.
La figure 4 montre comment l’API QSORT est appelée. Le prototype (en A) accepte des paramètres pour l’espace en mémoire servant au démarrage, le nombre d’éléments de la matrice, la taille de chaque élément, et l’adresse de la procédure chargée de la comparaison. J’utilise une routine différente pour chaque champ intervenant dans le tri, donc un groupe SELECT (en B) est utilisé pour préciser la routine de comparaison retenue.
Ensuite, j’appelle QSORT et lui ordonne d’utiliser cette routine de comparaison (en C).

La figure 5 montre l’une de ces routines de comparaison pour illustrer leur fonctionnement. On le voit, QSORT transmet à la routine de comparaison les deux éléments qu’elle veut comparer (en A). La routine les compare et renvoie 0 quand les clés ont les mêmes valeurs, 1 quand le premier élément devrait être placé plus loin dans la liste que le second élément, et -1 quand le premier élément devrait être placé avant le second élément (en B).
Pour modifier cette routine afin que le tri ait lieu dans l’ordre décroissant au lieu de croissant, j’inverserais les instructions RETURN afin que la condition plus petit que renvoie 1 et que la condition plus grand que renvoie -1.

Contrairement à SORTA, QSORT peut être utilisé sur de grandes matrices, sur de la mémoire allouée dynamiquement, et aussi sur des espaces utilisateur. Il peut trier une matrice MODS ou de structure de données ainsi que des matrices simples. Comme vous contrôlez la routine de comparaison, vous pouvez lui confier des tris insensibles à la casse et aussi l’utiliser pour des tris où la position de la clé varie. Elle est puissante et rapide. Cependant, elle présente un inconvénient. QSORT n’est pas un « tri stable ». Entendez par là que, même si QSORT met les champs clés dans le bon ordre lorsqu’il y a deux enregistrements dans lesquels les clés ont la même valeur, rien ne permet de prévoir lequel sera le premier et lequel sera le second (à moins, bien sûr, d’ajouter un autre champ de comparaison dans votre sous-procédure).