Récursivité

En programmation, la récursivité consiste en une fonction, ou une méthode, qui se rappelle elle-même.

Elle permet d'implémenter des algorithmes souvent mieux structurés, plus concis, et plus élégants. Par contre, l'appel de fonction et de méthode utilisant une pile statique en mémoire centrale, celle-ci peut déborder dans le cas où l'algorithme nécessite trop d'appels.

Tri rapide

Historique

En 1959, Tony Hoare est étudiant étranger à l’université de Moscou, et travail sur un système de traduction pour le laboratoire de physique nationale. Le dictionnaire utilisé était sur bande magnétique, donc en lecture séquentielle. Les mots à trouver devaient alors être en ordre alphabétique afin d’optimiser la recherche.

Les tris connus à ce moment étant trop lents, Hoare développe un algorithme d’échange de partition. Plus tard, il apprend le langage « ALGOL », supportant la récursivité, qui lui permet de perfectionner son algorithme pour finalement le publier dans le journal « Communications of the ACM, Volume 4, Issue 7 » en 1961 sous le nom de « QuickSort ».

Description

On peut considérer le tri rapide comme une amélioration du tri par sélection, c’est-à-dire que l’élément à trier est déplacé à sa position finale. L’amélioration repose sur le paradigme « diviser pour régner ».

Plutôt que de trouver le plus petit élément, comme le tri par insertion, le tri rapide se contente de trouver un élément pivot dans les éléments à trier. Tous les éléments se trouvant avant le pivot doivent être plus petits, et tous les éléments se trouvant après doivent être plus grands. À ce moment, l’élément pivot sera à sa position finale.

C’est là que le paradigme et la récursivité sont appliqués, puisque les mêmes opérations seront effectuées sur la partie de gauche et sur la partie de droite du pivot, jusqu’à ce que plus aucune partie ne reste à trier.

Algorithme

L’implémentation du tri rapide est relativement simple :

1. Appeler le tri rapide avec l’indice minimum et l’indice maximum, de la collection d’éléments à trier, comme paramètres.
2. Initialiser un indice « gauche » et un indice « pivot » à l’indice minimum ainsi qu’un indice « droite » à l’indice maximum :

        

1. Vérifier si l’élément à l’indice de gauche est supérieur à l’élément de l’indice de droite. Dans ce cas, interchanger les deux valeurs et mettre à jour l’indice pivot : si l’indice pivot est à l’indice de gauche, il faut le positionner à l’indice de droite, et vice-versa.
2. Les indices de gauche et de droite doivent toujours se rapprocher, donc si l’indice pivot est égal à l’indice de gauche, il faut décrémenter l’indice de droite, dans le cas contraire, il faut incrémenter l’indice de gauche.
3. Répéter les étapes 3 et 4 jusqu’à ce que les indices de gauche et de droite se rejoignent :

        

1. Finalement, utiliser la récursivité : si l’indice minimum est plus petit que l’indice pivot - 1, il faut rappeler le tri rapide avec la première partie des éléments à trier (de l'indice minimum jusqu’à l’indice pivot - 1), et si l’indice maximum est plus grand que l’indice pivot + 1, il faut rappeler le tri rapide avec la dernière partie (de l’indice pivot + 1 jusqu’à l'indice maximum) :