Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

Le tri étant décidément une réelle passion chez les informaticiens, nous allons étudier un nouvel algorithme de tri appelé l'algorithme de tri fusion (merge sort en anglais). Cet algorithme est intéressant car il peut être mis en œuvre de façon relativement efficace.

L'algorithme de tri fusion part de l'idée qu'il faut diviser pour mieux régner. Le principe est de prendre un tableau non trié et de le partitionner en deux parties à peu près égales. Ensuite, de façon récursive, l'algorithme trie le tableau de gauche et le tableau de droite. Enfin, l'algorithme fusionne les deux tableaux triés pour construire un tableau contenant tous les éléments triés. Cette opération de fusion est une opération relativement efficace car fusionner des tableaux triés est rapide en terme de temps de calcul.

Le schéma suivant illustre le principe. De façon récursive, l'algorithme commence par partitionner les tableaux jusqu'à obtenir des tableaux de taille 1. Ce tableau de taille 1 est naturellement trié. Ensuite, l'algorithme fusionne les tableaux de façon à reconstruire la liste triée.

La mise en œuvre que nous vous proposons dans cet exercice n'est pas optimisée, mais elle a l'avantage d'être relativement simple à comprendre. Cette mise en œuvre est subdivisée en trois parties. Dans la première partie, nous écrivons la méthode qui fusionne des tableaux triés. Dans la second partie, nous écrivons la méthode qui partitionne les tableaux. Enfin, dans la troisième partie nous complétons notre programme en utilisant les deux méthodes précédentes.

Une illustration fantaisiste de l'algorithme est donnée ici. la fusion Créez un projet nommé msort contenant une classe MergeSort, elle-même contenant une méthode main. Allouez le tableau d'entiers t1 initialisé avec les valeurs 3, 4, 7 et le tableau d'entiers t2 initialisé avec les valeurs 1, 2, 5, 9. Écrivez une méthode display prenant en argument un tableau d'entiers et l'affichant dans le terminal. Vérifiez que votre méthode est correcte en l'appelant avec l'argument t1. Avant de pouvoir fusionner les deux tableaux, nous avons besoin de deux méthodes annexes. La première méthode, nommée int[] right(int[] tab), alloue un tableau de taille tab.length - 1. Elle copie les éléments de droite du tableau tab (c.à-d., à partir de l'élément d'index 1) dans le tableau alloué et renvoie ce nouveau tableau. De façon à tester la méthode right, appelez la dans la méthode main avec l'argument t1, et vérifiez, en affichant le résultat de right avec display, que le nouveau tableau contient 4, 7. La seconde méthode annexe se nomme int[] merge(int val, int[] tab) et effectue l'opération inverse : elle renvoie un nouveau tableau dont le premier élément est val suivi d'une copie des éléments de tab. Vérifiez que votre méthode est correcte en affichant le résultat de merge(1, t1). Nous pouvons maintenant mettre en œuvre la fusion. Pour cela, vous allez écrire une nouvelle méthode nommée merge, prenant en argument deux tableaux t1 et t2 triés et renvoyant la fusion de ces deux tableaux. Le fait qu'il y ait deux méthodes merge ne pose pas de problème car les arguments des deux méthodes sont différents, ce qui permet à Java de savoir quelle méthode on souhaite appeler en fonction des paramètres.

Nous mettons en œuvre merge de façon récursive :
  • Si t1 a une taille égale à zéro, alors merge doit renvoyer t2
  • Si t2 a une taille égale à zéro, alors merge doit renvoyer t1
  • Si t1[0] est plus petit que ou égal à t2[0], alors merge doit renvoyer le tableau construit à partir de t1[0] et du résultat de la fusion de la partie droite de t1 avec le tableau t2. La partie droite de t1 s'obtient en appelant la méthode right et l'ajout à gauche de t1[0] s'obtient en appelant la seconde méthode merge que vous avez défini à la question précédente.
  • Dans le cas inverse, il suffit d'appeler merge en inversant les rôles de t1 et t2.

Testez merge en affichant le résultat de la fusion de t1 et t2 dans la méthode main.
le partitionnement Dans cette partie, nous nous occupons de partitionner un tableau. Commencez par supprimer les tests actuels de la méthode main (les définitions des t1 et t2 incluses). À la place, allouez un tableau d'entiers nommé tab initialisé à 4, 7, 3, 9, 1, 2, 5. Écrivez une méthode int[] extract(int[] tab, int start, int end) qui extrait de tab le sous-tableau commençant à l'indice start inclus et finissant à l'indice end non inclus. Testez votre méthode extract en affichant le résultat de l'extraction de la moitié gauche de tab dans la méthode main. Vous devriez obtenir le tableau 4, 7, 3. le tri fusion Nous pouvons enfin mettre en œuvre l'algorithme du tri-fusion. Écrivez une méthode int[] mergeSort(int[] tab) mettant en œuvre l'algorithme de tri fusion pour renvoyer un tableau contenant les éléments de tab triés. Pour vous guider, nous vous proposons d'utiliser un algorithme récursif :
  • Si tab a une taille inférieure ou égale à 1, alors le tableau est déjà trié et il suffit de le renvoyer.
  • Sinon, il faut appeler mergeSort sur la partie gauche de tab, puis mergeSort sur la partie droite de tab et enfin utiliser merge pour fusionner les résultats des deux appels à mergeSort.
Félicitations ! Vous venez de mettre œuvre votre premier algorithme complexe en Java !