Pale Machine - Tri
Jean-Christophe Filliâtre

Introduction

Le but de cet examen est d'écrire plusieurs algorithmes de tri, sur des listes et des tableaux d'entiers.

L'examen contient trois exercices indépendants. L'exercice 1 considère le tri d'une liste par la méthode du tri fusion (mergesort). Les exercices 2 et 3 concernent le tri de tableaux. L'exercice 2 étudie le cas particulier d'un tableau dont les éléments ne prennent que trois valeurs distinctes. L'exercice 3 considère l'algorithme quicksort.

Pour chaque exercice, un fichier contenant deux classes est fourni. Une classe doit être complétée ; l'autre est fournie dans le but de tester votre code.

Note : Vous n'avez pas accès au réseau mais vous pouvez néanmoins consulter la documentation Java en local.

1. Tri d'une liste par la méthode du tri fusion

On s'intéresse ici au tri de listes d'entiers de type LinkedList<Integer> par la méthode du tri fusion.

Un fichier Ex1.java est fourni. Il contient deux classes.

La classe Mergesort contient les trois méthodes que vous devez compléter dans les questions 1.1 à 1.3.

La classe Ex1 contient le code pour effectuer les tests. Elle ne doit pas être modifiée. C'est la méthode main de cette classe qu'il faudra exécuter pour tester vos réponses.

Question 1.1 : partage

Écrire le code de la méthode split qui prend en arguments trois listes l, l1 et l2 et partage les éléments de l entre les listes l1 et l2. Plus précisément, on fait l'hypothèse qu'initialement Au final, la méthode split doit assurer le résultat suivant :

On pourra procéder en parcourant l et en mettant ses éléments alternativement dans l1 et l2.

Question 1.2 : fusion

Écrire le code de la méthode merge qui prend en argument deux listes l1 et l2, supposées triées dans l'ordre croissant, et renvoie une liste triée contenant l'ensemble des éléments de l1 et l2.

Les listes l1 et l2 peuvent être modifiées.

Question 1.3 : tri

Enfin, écrire le code de la méthode mergesort qui prend en argument une liste l et la trie de la manière suivante :
  1. si l contient 0 ou 1 élément, elle est renvoyée telle quelle ;
  2. sinon,
    1. on découpe la liste l en deux listes l1 et l2 avec split,
    2. on trie récursivement l1 et l2 avec mergesort,
    3. on fusionne les deux résultats avec merge.

La liste l passée en argument à mergesort ne doit pas être modifiée.

Tester avec la classe Ex1 fournie.

Déposer le fichier Ex1.java :

2. Le drapeau hollandais de Dijkstra

On s'intéresse maintenant au tri de tableaux d'entiers. Dans cet exercice, on considère le cas particulier d'un tableau dont les éléments ne prennent que trois valeurs possibles. C'est un problème historique posé par Dijkstra sous le nom de problème du drapeau national hollandais, les trois valeurs possibles étant les trois couleurs bleu, blanc et rouge. Ici, on considère que les trois valeurs possibles sont 0, 1 et 2. Bien entendu, il serait très facile de trier un tel tableau en se contentant de compter le nombre d'occurrences des trois valeurs 0, 1 et 2. Cependant, on s'impose ici de ne procéder que par des tests et des échanges (on peut imaginer des valeurs plus complexes que des entiers, et toutes distinctes, mais appartenant à trois catégories différentes).

Un fichier Ex2.java est fourni. Il contient deux classes. La classe DutchFlag contient les deux méthodes que vous devez compléter dans les questions 2.1 et 2.2. La classe Ex2 contient le code pour effectuer les tests. Elle ne doit pas être modifiée. C'est la méthode main de cette classe qu'il faudra exécuter pour tester vos réponses.

2.1. Échange

Écrire le code de la méthode swap qui prend en arguments un tableau a, deux indices i et j dans les bornes de ce tableau, et échange le contenu des cases i et j de a.

2.2. Tri

Pour résoudre le problème du drapeau hollandais, on se propose de procéder ainsi. On divise le tableau a en quatre zones à l'aide d'indices b, i et r de la manière suivante
 0          b          i          r           n
+----------+----------+----------+-----------+
|    0     |    1     |     ?    |      2    |
+----------+----------+----------+-----------+
n désigne la longueur du tableau. L'intervalle [0,b[ ne contient que des 0 ; l'intervalle [b,i[ ne contient que des 1 ; et l'intervalle [r,n[ ne contient que des 2. L'intervalle [i,r[ correspond à la portion du tableau restant à traiter. La notation [x,y[ désigne un intervalle fermé à gauche et ouvert à droite. Notez que chacun de ces intervalles peut être vide.

Initialement, on a b=i=0 et r=n. Puis on effectue une boucle while (i < r) qui examine a[i] et, selon le cas, met à jour les indices et/ou procède à un échange à l'aide de la méthode swap.

Tester avec la classe Ex2 fournie.

Déposer le fichier Ex2.java :

3. Quicksort

On considère maintenant le cas d'un tableau d'entiers quelconque. On se propose de le trier à l'aide de l'algorithme quicksort, encore appelé tri rapide.

Un fichier Ex3.java est fourni. Il contient deux classes. La classe Quicksort contient les trois méthodes que vous devez compléter dans les questions 3.1 à 3.4. La classe Ex3 contient le code pour effectuer les tests. Elle ne doit pas être modifiée. C'est la méthode main de cette classe qu'il faudra exécuter pour tester vos réponses.

3.1. Échange

Écrire le code de la méthode swap qui prend en arguments un tableau a, deux indices i et j dans les bornes de ce tableau, et échange le contenu des cases i et j de a. Notez que c'est la même fonction qu'à l'exercice 2.1 ; on pourra donc récupérer le code correspondant.

3.2. Partitionnement

Écrire le code de la méthode partition qui prend en arguments un tableau a, deux indices l et r tels que 0 <= l < r < a.length, qui réarrange les éléments du segment a[l..r] et enfin qui renvoie un indice m dans cet intervalle tel qu'on ait la situation suivante :
   l          m          r
  +----------+-+----------+
  |   < v    |v|   >= v   |
  +----------+-+----------+
c'est-à-dire uniquement des valeurs inférieures à a[m] à gauche de m et uniquement des valeurs supérieures ou égales à a[m] à droite de m. (Le contenu du tableau a en dehors de a[l..r] n'est pas modifié.)

Pour cela on pourra procéder de la manière suivante. On choisit v=a[l]. On divise alors le segment a[l+1..r] en trois zones à l'aide de deux indices m et i, de la manière suivante :

 l         m            i         r
+-+---------+----------+-----------+
|v|   < v   |   >= v   |     ?     |
+-+---------+----------+-----------+
Initialement on a m=l. On parcourt alors l'intervalle l+1..r de la gauche vers la droite avec l'indice i et, selon le cas, on met à jour m et on procède à un échange. Une fois ce parcours terminé, il ne reste plus qu'à échanger les éléments a[l] et a[m] et on obtient bien la situation ci-dessus.

3.3. Tri récursif

Écrire le code de la méthode quickrec qui prend en arguments un tableau a, deux indices l et r tels que 0 <= l et r < a.length, et trie le segment a[l..r] du tableau a par la méthode du tri rapide.

L'idée consiste à procéder récursivement, de la manière suivante :

3.4. Tri

En déduire le code de la méthode quicksort qui trie l'intégralité d'un tableau.

Tester avec la classe Ex3 fournie.

Déposer le fichier Ex3.java :