Admin CliCours
1. Utilisez une variable temporaire pour stocker l’une des deux valeurs des variables à échanger avant de l’écraser en la remplaçant par la valeur de l’autre variable. Ce dia- gramme met bien en avant le flot des valeurs. La variable temporaire est représentée par un pin.
Comme vous n’avez pas plus de précisions sur le type des objets contenus dans le tableau, utilisez un template pour représenter ce type : l’opération est en effet générique et valable quel que soit le type T contenu dans le tableau.
2. Le diagramme de la figure 5.23 présente une structure intéressante pour la représentation de boucles, qui fait apparaître clairement les deux boucles imbriquées. Les cycles dans le graphe traduisent le phénomène de bouclage , et l’imbrication est visible grâce à la hiérarchie.
Le placement des objets constituant les boucles (corps de boucle, condition d’arrêt…) est reconnaissable visuellement ; il est réutilisé plusieurs fois dans les diagrammes qui suivent.
Deux points de décision font apparaître plus clairement à la fois le début et la fin de l’alternative dans la boucle interne.
Une nouvelle contrainte sur le type contenu dans le tableau impose que ce type soit muni d’une relation d’ordre total pour que puisse s’opérer la comparaison de ses éléments. Indiquez-la en mentionnant que le type T doit réaliser l’interface Comparable. (Voir aussi la section 3.3 et l’exercice 4 du chapitre 3.)
3. Cette version du tri limite le nombre de copies intermédiaires de valeur. Elle réalise un « roulement » des variables (au lieu de les échanger deux à deux) qui déplace tout un bloc avant de recopier la variable temporaire.
La structure de l’algorithme reste assez proche du tri par bulles. De ce fait, il a la même complexité théorique en O(n2) en nombre d’opérations que le tri par bulles, mais réalise un peu moins de copies que lui. Vous vous en apercevrez en comparant les deux schémas : l’imbrication des deux boucles apporte le facteur n2 et les différences entre les actions dans chaque boucle n’apportent qu’un facteur constant, donc théoriquement négligeable en complexité.
4. Le tri par fusion permet de montrer la modélisation de concepts algorithmiques avancés, en particulier la récursivité et le parallélisme. Ce type de tri est relativement puissant : il a une complexité comparable au quicksort, devenu standard, et se prête également à une implémentation sur des listes chaînées. C’est récemment devenu l’algorithme de tri standard (au lieu de quicksort) du langage Perl par exemple.
Comme le montre le diagramme présenté à la figure 5.25, il est possible de l’implémenter avec des traitements en parallèle, ce qui se prête aux architectures parallèles. Pour autant, il n’est pas obligatoire de l’implémenter avec du parallélisme : toute exécution qui respecte l’enchaînement des actions et les barres de synchronisation est correcte.
Les numéros indiqués à côté des pins donnent l’ordre des arguments. L’appel récursif est représenté comme un appel de fonction normal.
L’algorithme correspond à l’approche « diviser pour régner ». À chaque profondeur dans l’appel récursif, vous triez un tableau deux fois plus petit : la moitié du tableau précédent. La complexité théorique totale des traitements n’est qu’en O(n log n), au lieu de O(n2), comme les deux algorithmes précédents.
