ALGORITHMIQUE

Méthodes de tri

Le problème du tri consiste, étant donné une suite x = (x₁, x₂, ..., x_n) d'éléments d'un ensemble totalement ordonné – par exemple N ou R –, à déterminer une permutation σ de 1, ..., n telle que :

L'algorithme de tri par échanges consécutifs, TEC, est conceptuellement le plus simple. Il consiste en (n − 1) phases successives :

La complexité d'un algorithme de tri tel que TEC se mesure par le nombre de comparaisons effectuées et par le nombre de déplacements d'éléments de la suite (sur l'exemple, dix comparaisons et sept échanges). Dans le cas de l'algorithme TEC appliqué à une suite de longueur n, le nombre de comparaisons vaut exactement :

De nombreux algorithmes de tri élémentaires possèdent une complexité en O(n²). Comme dans le cas des algorithmes arithmétiques, une conception récursive conduit à une réduction importante de complexité.

L'algorithme de tri-fusion est ainsi fondé sur le principe suivant : Supposons n pair, n = 2 m ; pour trier x₁, x₂, ..., x_n, on trie séparément x₁, x₂, ..., x_m et x_m+1, x_m+2, ..., x_n. Soit u = (u₁, u₂, ..., u_m) et v = (v₁, v₂, ..., v_m) les résultats de ces deux tris. On obtient la suite y correspondant au tri de x par la fusion (ou interclassement) des suites u et v, l'algorithme de fusion étant défini récursivement par :

Parmi les autres méthodes de tri récursif de complexité O(n log n), la plus connue est le tri-partition, encore appelé « tri rapide » (Hoare, 1962). Le tri-partition de x = (x₁, x₂, ..., x_n) correspond à la suite de calculs :

(a) séparer x en deux sous-ensembles x′, x″ :

(b) trier séparément x′ et x″, avec pour résultats y′ et y″ ;

(c) retourner le résultat global y = y′ ( y″.

L'algorithme de tri-fusion est à la base des méthodes de tri externe appliquées aux fichiers sur disque. L'algorithme de tri-partition, convenablement optimisé, est le plus rapide pour les tris en mémoire centrale d'ordinateur.

Structures de données

Une autre approche du problème du tri repose sur la construction de structures de données : il s'agit de la superposition à l'ensemble des données (un simple vecteur dans le cas du tri) d'une structure plus riche permettant un accès plus rapide aux informations ainsi complétées.

La structure de donnée la plus importante en informatique est certainement la structure d'arbre (graphe connexe sans cycle). Étant donné une suite x = (x₁, x₂, ..., x_n), un arbre[...]