> Avant de commencer ce td, n’oubliez pas de faire le quiz, attention temps limité.
Rappels sur la configuration de vscode
Commencez par créer un nouveau projet java dans Visual Studio Code pour le TD d’aujourd’hui (voici tous les détails). En gros il faut :
créer un projet java par le menu Create Java Project qui ouvre un dialogue, dans lequel on choisit No build tools
choisir l’emplacement du projet (ex. dans le dossier INF361 qui contiendra tous vos projets java de INF361)
donner un nom au projet (ex.
TD5)Configurez votre projet pour l’utilisation de
TC(voici tous les détails concernant son installation et utilisation). N’oubliez pas d’ajouter au début de vos programmes la ligneimport tc.TC;
Enregistrer les archives compressées FichiersTxt.zip et FichiersJava.zip. Extraire les
fichiers de la première archive (les fichiers .txt) à la
racine du projet TD5, et les fichiers de
la seconde (les fichiers .java) dans le dossier
src du projet TD5.
(Pour extraire les fichiers contenus dans cette archive à l’aide de l’explorateur de fichiers, double-cliquer sur l’archive : une fenêtre devrait alors s’ouvrir et proposer d’en extraire le contenu.)
Une entreprise souhaite recruter plusieurs salariés au niveau
national. Pour cela, elle a évalué des candidats par une note et stocké
les résultats dans le fichier candidats.txt. Dans ce TD, on
souhaite écrire un ensemble de programmes pour permettre à l’entreprise
de traiter les données et de sélectionner les meilleurs candidats. Votre
but dans cette section du TD est de lire les informations sur les
candidats et de les stocker dans des objets que l’on utilisera dans les
sections suivantes.
On souhaite stocker toutes les informations sur chaque candidat dans
un objet de la classe Candidat qui est définie dans le
fichier Candidat.java. On donne deux constructeurs. Le
premier initialise l’objet avec les arguments nom,
prenom, note et dossierId qu’il
faut stocker dans l’objet. Le second initialise un Candidat
à partir d’une chaîne de la forme
"nom prénom note dossierId". En outre, on donne une méthode
toString pour retourner une chaîne de la même forme à
partir de l’objet courant.
Implémentez les méthodes de la classe Candidat. Pour
découper l’entrée du deuxième constructeur, vous pouvez vous servir de
la methode TC.motsDeChaine.
Pour convertir un String dans un int, la
methode Integer.parseInt
est utile.
L’identifiant de dossier est composé de trois chiffres et d’une
lettre. Il est représenté dans le champ dossierId qui est
un objet de la classe DossierId. Il vous faut utiliser le
constructeur DossierId(String s) pour le construire à
partir d’une chaîne de caractères.
Lancez TestExercice1 pour tester votre code.
TestExercice1 devrait écrire un fichier
SortieExercice1.txt que vous pouvez comparer aux résultats
attendus dans ReferenceExercice1.txt comme dans le TD
3.
Vérifiez que votre code donne le bon résultat et déposez ici
le fichier Candidat.java.
On veut maintenant lire tous les candidats qui se trouvent dans le
fichier candidats.txt. Dans ce fichier on trouve les
informations dans le format suivant : la première ligne donne le nombre
n de candidats dans le fichier, suivie de n
lignes qui contiennent des chaînes de la forme
"nom prénom note dossierId". Dans cet exercice, nous lirons
tous les candidats pour les stocker dans un tableau.
Pour créer et remplir un tableau de type Candidat[] on
utilisera la classe CandidatUtil. Dans cette classe on
trouve la méthode
public static Candidat[] readCandidatsFromFile(String nomDuFichier)
qui prend comme argument le nom nomDuFichier d’un fichier
et donne un Candidat[] qui contient des objets de la classe
Candidat représentant chacun des candidats dans le
fichier.
Complétez la méthode
public static Candidat[] readCandidatsFromFile(String nomDuFichier)
de CandidatUtil. Pour lire un fichier, vous pouvez utiliser
les méthodes de la classe TC : TC.lectureDansFichier
et TC.lireLigne.
Après avoir lu le fichier, vous pouvez revenir au comportement initial
de lecture sur entrée standard en appelant TC.lectureEntreeStandard.
Attention! Il est
recommandé de ne pas utiliser d’autres fonctions de
lecture, comme TC.lireInt(), en combinaison avec
TC.lireLigne(). Il faut lire toute l’entrée, ligne par
ligne, avec TC.lireLigne() et, si le cas se présente,
interpréter le contenu d’une ligne comme un entier à l’aide de
Integer.parseInt.
Lancez TestExercice2 pour tester votre code.
TestExercice2 devrait écrire un fichier
SortieExercice2.txt que vous pouvez comparer aux résultats
attendus dans ReferenceExercice2.txt. Vérifiez que votre
code donne le bon résultat et déposez ici
le fichier CandidatUtil.java.
Dans cette partie du TD on compare les candidats deux à deux pour savoir dans quel ordre les placer. On dit qu’on se place dans le cadre du modèle de comparaison pour trier les candidats. La partie II sortira de ce cadre.
Les mêmes candidats peuvent être munis de différentes relations
d’ordre total, c’est à dire que deux candidats c1
et c2 sont toujours dans un des trois cas suivants :
c1 < c2, c1 = c2, ou
c1 > c2. Deux exemples d’ordres totaux : l’ordre de
note, et l’ordre lexicographique nom puis prénom.
Définir un ordre total revient à implémenter une méthode
int compare(Candidat c1, Candidat c2) qui doit retourner
:
un entier strictement négatif (quel qu’il soit) si
c1 est strictement plus petit que c2 pour la
relation d’ordre qu’on souhaite définir,
0 si c1 et c2 sont égaux
pour cet ordre,
un entier strictement positif (quel qu’il soit) si
c2 est strictement plus petit que c1.
Comment utiliser deux ordres différents avec le même nom de fonction
? Il nous suffira de donner deux implémentations de la même
interface CandidatComparator.
L’interface CandidatComparator est déjà définie dans
CandidatComparator.java. Il s’agit simplement d’une
extension de l’interface java.util.Comparator<T> de
la bibliothèque standard java qui déclare une seule méthode
int compare(T o1, T o2) comme ci-dessus. La syntaxe
<T> signifie que Comparator est
générique et définit une interface pour toute classe T,
mais nous nous intéressons ici uniquement à la classe
Candidat. On définit ainsi CandidatComparator
comme une interface spécialisée
Comparator<Candidat>.
En conclusion il faut et il suffit de définir la méthode
int compare(Candidat c1, Candidat c2) dans toute classe qui
implémente l’interface CandidatComparator.
compare dans la classe
CandidatComparatorNote pour l’ordre de note. Testez alors
avec la classe Essai3, ou en recopiant
import tc.TC;
public class Essai3{
public static void main(String[] args){
CandidatComparatorNote comp = new CandidatComparatorNote();
Candidat c1 = new Candidat("STIGNY MARIE 16 127S");
Candidat c2 = new Candidat("PAPIELLER MARIE 11 120P");
TC.println("c1="+c1);
TC.println("c2="+c2);
TC.println(comp.compare(c1, c2));
}
}
Vous devez obtenir comme output
c1=STIGNY MARIE 16 127S c2=PAPIELLER MARIE 11 120P 1
(Le nombre sur la dernière ligne peut éventuellement être remplacé par un autre entier strictement positif.)
Implémentez les méthodes compare dans les classes
CandidatComparatorNom (pour l’ordre lexicographique : on
compare les noms puis les prénoms si besoin)
CandidatComparatorId (pour l’ordre par identificateur de
dossier). Pour la comparaison de deux Strings, on peut
s’aider de la méthode d’objet compareTo(String)
de la classe String. Pour la comparaison de deux
DossierIds, il faut utiliser la méthode d’objet
compareTo(DossierId) de DossierId.
Lancez TestExercice3 pour tester votre code. On utilise
la fonctionnalité standard de java pour trier des objets, en particulier
la méthode générique Arrays.sort
qui prend comme arguments
un tableau de type T[] qui contient les éléments à
trier, et
un Comparator<T> pour comparer les éléments
dans le tableau.
TestExercice3 devrait écrire un fichier
SortieExercice3.txt que vous pouvez comparer aux résultats
attendus dans ReferenceExercice3.txt. Vérifiez que votre
code donne le bon résultat et déposez ici
les fichiers CandidatComparatorNote.java,
CandidatComparatorNom.java,
CandidatComparatorId.java.
Comme vous l’avez vu dans l’exercice 3, trier des objets en java est
simple : il faut seulement coder un Comparator et après
utiliser Arrays.sort.
En fait, c’est l’approche recommandée en pratique parce que les
algorithmes fournis par java sont fortement optimisés et montrés
corrects. Néanmoins, pour mieux comprendre les algorithmes de tri, nous
allons manuellement coder certains de ces algorithmes dans la suite.
Les algorithmes de tri que nous allons écrire manuellement seront chacun écrits dans une classe séparée.
On choisit comme premier algorithme de tri le tri par
sélection, autrement dit par sélection itérée du plus petit
élément. Pour cela, on vous demande de compléter la méthode
trier de la classe TriSelection.
Une description détaillée de l’algorithme que vous aurez à coder est fournie au Chap. 10 du poly du cours CSC_3X061_EP. Les transparents de l’Amphi 5 fournissent également une illustration de cet algorithme. Vous pouvez aussi jeter un coup d’œil à Wikipedia ici.
Lancez TestExercice4. Ce test devrait écrire deux
fichiers fichiers SortieExercice4a.txt et
SortieExercice4b.txt que vous pouvez comparer aux résultats
attendus dans ReferenceExercice4a.txt et
ReferenceExercice4b.txt. Quand tous les résultats des tests
sont bons, déposez TriSelection.java ici.
On choisit comme second algorithme de tri le tri par
insertion, autrement dit le maintien d’une première partie de
tableau déjà triée en insérant chaque nouvel élément au bon endroit.
Pour cela, on vous demande de compléter la méthode trier de
la classe TriInsertion.
Une description détaillée de l’algorithme que vous aurez à coder est fournie au Chap. 10 du poly du cours CSC_3X061_EP. Les transparents de l’Amphi 5 fournissent également une illustration de cet algorithme. Vous pouvez aussi jeter un coup d’œil à Wikipedia ici.
Votre tri par insertion doit vérifier la propriété suivante
: si une entrée x est devant y avant le tri et
si les deux entrées sont égales, alors x est aussi devant
y après le tri. Intuitivement, l’algorithme change l’ordre
des entrées seulement si c’est absolument nécessaire. On appelle un
algorithme avec cette propriété un algorithme de tri stable. En
pratique, ce type d’algorithme est souvent souhaitable, surtout quand on
veut enchaîner plusieurs tris (on verra cela plus tard dans l’Exercice
8).
Lancez TestExercice5. Ce test devrait écrire deux
fichiers SortieExercice5a.txt et
SortieExercice5b.txt que vous pouvez comparer aux résultats
attendus dans ReferenceExercice5a.txt et
ReferenceExercice5b.txt.
Quand tous les résultats des tests sont bons, déposez
TriInsertion.java ici.
Compiler Benchmarks.java et exécuter le. Cela produit
deux fichiers selection.in et insertion.in
qu’on peut afficher à l’aide de gnuplot (en Linux, sur les
stations). Pour ce faire
gnuplot
gnuplot> plot "selection.in", "insertion.in"affiche une fenêtre avec les points affichés. Que pensez-vous du résultat ?
Il n’y a rien à déposer.
Comme vous l’avez vu en cours, le tri par tas fait
O(n log(n)) opérations pour trier n éléments.
On peut montrer que ce nombre d’opérations est asymptotiquement optimal
dans le modèle de comparaison, c’est-à-dire qu’il n’y aucun algorithme
basé seulement sur les comparaisons qui fait moins d’opérations.
Dans cette partie du TD, nous considérons des algorithmes de tri qui n’utilisent pas de comparaisons entre les éléments. Au lieu de cela, on utilisera des propriétés des attributs qui donnent l’ordre des objets. On verra que cela peut donner des algorithmes plus efficaces.
L’algorithme CountingSort est surtout intéressant dans le cas où on
veut trier des éléments qui ont peu de valeurs différentes. Pour
simplifier les explications, nous considérons d’abord un tableau
a d’entiers positifs que nous voulons trier. Nous supposons
que ces entiers sont compris entre 0 et k
inclus.
L’idée de CountingSort est de calculer pour chaque élément
a[i], en position i dans le tableau initial,
combien d’autres éléments de a seront avant
a[i] une fois le tableau trié. Ainsi on pourra placer
a[i] directement à sa position. Ce calcul est très facile
quand chaque valeur ne peut apparaître qu’une seule fois. Quand chaque
valeur peut apparaître plusieurs fois, le calcul se complique un
peu.
Notre algorithme va utiliser deux tableaux additionnels :
un tableau b de la même taille que a
qu’on utilisera pour un stockage temporaire, et
un tableau count, de taille k + 1 dont
chaque case count[i] contient une position où il faut
insérer le prochain élément de valeur i.
Voici une description de l’algorithme CountingSort :
en parcourant le tableau a une seule fois, stocker
dans chaque count[v] le nombre d’occurrences de la valeur
v dans le tableau a
count[0] = count[0] - 1
Pour chaque i de 1 à k, faire
count[i] = count[i] + count[i-1]
(count[i] est la dernière position pour un élément de
valeur i)
pour chaque position i dans a en
commencant par la fin, faire :
b[count[a[i]]] = a[i]
count[a[i]]--b dans aOn vérifie facilement que l’algorithme trie le tableau correctement. On voit aussi que l’algorithme est stable.
Nous voulons maintenant coder l’algorithme CountingSort. Comme on ne
veut pas seulement trier des entiers mais des objets de type
Candidat, il nous faut encore quelques préparations. En
fait, nous avons besoin d’une manière d’associer une valeur numérique à
chaque Candidat. Pour cela, nous introduisons une interface
CountingSortAdapter avec deux méthodes :
int getMaxValue() renvoie la valeur maximale qu’on
utilise pendant le tri (dans l’algorithme ci-dessus, c’est
k). Cette valeur (plus 1) donne la taille de
count dans l’algorithme.
int getValue(Candidat element) donne la valeur qui
représente l’élément dans l’ordre qu’on désire. Dans l’algorithme
ci-dessus, il s’agit simplement de la valeur a[i], mais
pour des objets plus complexes que des entiers, la définition peut être
différente et dépend de l’ordre.
On triera des Candidats dans l’ordre croissant donné par
leur notes, c’est-à-dire que par exemple un Candidat avec
la note 4 est devant un Candidat avec la note
15. Une implémentation de l’interface
CountingSortAdapter vous est fournie par la classe
CandidatCountingSortAdapterNote.
Codez l’algorithme CountingSort en complétant la méthode
trier de la classe TriComptage qui vous est
fournie. Il y a un CountingSortAdapter adapter
que vous devez utiliser pour le tri.
Testez votre code avec la classe TestExercice7.java.
Cette classe crée un fichier SortieExercice7.txt que vous
pouvez comparer à ReferenceExercice7.txt pour vérifier que
votre code est correct. Après, déposez votre
TriComptage.java ici.
Nous avons vu que l’on peut bien utiliser CountingSort si le nombre
de valeurs à trier est limité. Si on ne connaît pas ces valeurs à
l’avance ou s’il y a trop de valeurs possibles, CountingSort n’est pas
utile parce qu’on ne peut pas créer le tableau count ou il
devient trop grand pour être efficace.
Notre dernier algorithme peut résoudre le deuxième problème dans le cas où les valeurs à trier sont des chaînes de caractères de taille fixe. C’est par exemple souvent le cas pour les numéros de client, les numéros de carte d’identité ou les IBAN. Pour cet exercice, nous allons trier les candidats par leur numéro de candidat qui consiste en une chaîne de 4 chiffres et lettres.
L’algorithme qu’on va utiliser s’appelle RadixSort. La première étape est d’appliquer un algorithme de tri stable (pour nous, CountingSort) pour trier les entrées selon le caractère en dernière position. La deuxième étape est un tri stable selon le caractère en avant-dernière position. On itère jusqu’à effectuer un tri stable selon le caractère en première position. On obtient alors un tableau complètement trié. Alors, l’algorithme pour trier un tableau data de chaînes de d caractères est :
pour toutes les positions i de d-1 à 0
appelle CountingSort pour trier data dans l'ordre donné par les entrées dans data dans la position iRegardez par exemple la séquence de chaînes
["321", "222", "221", "212"]. On trie d’abord dans l’ordre
donné par la troisième position et on obtient
["321", "221", "222", "212"]. Le tri de la deuxième
position donne ["212", "321", "221", "222"]. Finalement, le
dernier tri donne ["212", "221", "222", "321"], le résultat
correct.
Réfléchissez pourquoi l’algorithme est correct. Complétez ensuite la
méthode trier de TriRadix. Utilisez
l’interface RadixSortAdapter qui a deux méthodes :
int getNumberOfDigits() renvoie le nombre de
caractères dans les chaînes qu’on utilise pour le tri.
CountingSortAdapter getCountingSortAdapter(int pos)
renvoie un CountingSortAdapter que l’on peut utiliser pour
trier dans l’ordre donné par la position pos.
Testez votre code avec TestExercice8 comme dans
l’Exercice 5 et déposez TriRadix.java ici.