Le tri rapide ou Quick sort |
Encore une méthode de tri. Comme son nom l'indique cette méthode de tri est la plus rapide. Lorsque l'on dit la plus rapide cela signifie dans le cas général ou dans le cas le pire. Quoi qu'il en soit cette méthode est des plus intéressantes car l'algorithme de tri rapide est un algorithme récursif qui illustre parfaitement la puissance de la programmation récursive.
Vous connaissez le problème, je ne reviens pas dessus. Le quick sort consiste à appliquer une méthode bien connue de la programmation et de la politique: Diviser pour régner (divide and conquer).
Si en termes politiques diviser signifie créer des dissensions internes, en informatique cela signifie couper le problème en deux ou plus. En effet, la méthode consiste à choisir un élément pivot à peu près en milieu de liste puis à mettre à sa gauche tous les éléments qui lui sont inférieurs et à sa droite tous les éléments qui lui sont supérieurs (pour un tri dans l'ordre croissant bien sūr). Une fois cette opération effectuée, il suffit de réitérer le processus sur la liste restant à gauche du pivot et sur celle restant à sa droite.
Ex :
[12 -8 5 -32 -3] 5 est pivot
[-3 -8 -32 5 12] les < à 5 sont à gauche les autres à droite (le pivot a bougé !)
[-3 -8 -32] recommence sur la liste gauche
[-32 -8 -3] liste gauche triée
[5 12] recommence liste droite
[5 12] liste droite trîée
[-32 -8 -3 5 12] liste triée finale
Nul besoin de revenir sur les procédures d'entrée et de sortie des entiers, il est bien évident que vous devez réutiliser celles écrites pour les tris simples.
La procédure de tri rapide prendra en paramètre, outre la liste à trier et sa taille, l'indice de début de tri et celui de fin de tri. Ce sont ces deux indices qui nous permettront de nous rappeler récursivement sur des parties de la liste.
Vous utiliserez donc deux variables i et j, une partant du début de la liste et l'autre de la fin. Ces variables seront incrémentées jusqu'à trouver un élément mal placé par rapport au pivot. Une fois les variables i et j pointées sur des éléments mal placés, il suffit de faire la permutation et d'incrémenter (décrémenter) les variables.
Je vous propose maintenant de mettre en application ce magnifique algorithme de tri. Pour ce faire, je vous demande de reprendre votre programme et de l'adapter pour qu'il puisse trier un jeu de 32 cartes. Les cartes seront représentées par une structure de type article à deux champs : un champs couleur (carreau, pique trefle, coeur) et un champs niveau (1, 7, 8, 9, 10, V, D, R). Vous programmerez dons :