Java

public class Trieuse {
/**
* effectue le tri par insertion d'un vecteur d''el'ements comparables.
* v le vecteur 'a trier
* retourn un vecteur tri'e par ordre croissant
* lance NonComparableException si v contient un 'el'ement de type
* non Comparable ou si v contient deux 'elements de type
* (classe) diff'erents
*/
public static Vector triInsertion(Vector v) throws NonComparableException{
Vector res = new Vector(); // le vecteur r'esultat
int i; // indice pour le parcours de v
int p; // indice pour la position d'insertion dans res
for (i=0; i < v.size(); i++){
// on verifie que l''el'ement i de v est bien un 'el'ement Comparable
// si ce n'est pas le cas, envoi d'une exception
if (! (v.elementAt(i) instanceof Comparable))
throw new NonComparableException("element " + i +
"du vecteur n'est pas un Comparable");
// on range dans elti le i'eme 'el'ement de v
Comparable elti = (Comparable) v.elementAt(i);
// recherche de la position p de elti dans le vecteur resultat
p = 0;
while(p < res.size()&& !(elti.plusPetitQue(res.elementAt(p)))) p++;
// insertion de elti 'a la position p dans le vecteur resultat
res.insertElementAt(elti,p);
}
return res;
}
}
La m'ethode triInsertion permet de trier par ordre croissant des vecteurs quelconques
'a condition qu'ils contiennent des 'el'ements instances de classes impl'ementant l'interface
Comparable d'efinie comme suit :
public interface Comparable {
/**
* comparaison de deux 'el'ements.
* o objet avec lequel le recepteur du message doit se comparer.
* retourne true si this et o sont de m^eme classe et si
* this est plus petit que o selon la relation de comparaison d'efinie pour
* la classe de this. false sinon
* lance NonComparableException si this et o ne sont pas de m^eme classe.
*/
public boolean plusPetitQue(Object o) throws NonComparableException;
}
La classe des exceptions pouvant ^etre lanc'ees par les m'ethodes plusPetitQue et triInsertion
est quant 'a elle d'efinie de la mani'ere suivante :
1
public class NonComparableException extends Exception {
public NonComparableException(String message) {
super(message);
}
}
1.1 Quel est le r^ole de l'interface Comparable dans le programme ci-dessus ? Pourquoi utiliser
une interface plut^ot qu'une classe abstraite dans ce cas pr'ecis ?
1.2 Pourquoi est il n'ecessaire de forcer le type du r'esultat (cast) dans l'affectation suivante
extraite de la m'ethode triInsertion ?
Comparable elti = (Comparable) v.elementAt(i) ;
1.3 La classe NonComparableException h'erite de la classe Exception sans red'efinir ni
m'ethode ni attribut. Quel est alors l'int'er^et de cet h'eritage ?
1.4 Pour tester la m'ethode de tri par insertion, on va l'appliquer 'a un vecteur d'entiers, la
relation d'ordre utilis'ee 'etant la relation d'ordre habituelle sur les entiers.
a. Ecrivez une classe EntierComparable encapsulant sous forme d'objets des entiers (type
primitif int) qui pourront ^etre exploit'es par la m'ethode de tri par insertion de la classe
Trieuse.
b. Ecrivez un programme principal permettant le test de la m'ethode triInsertion. Ce
programme devra cr'eer un vecteur de 20 EntierComparables dont la valeur est tir'ee
au hasard dans l'intervalle [0..100], afficher ce vecteur, lui appliquer un tri par insertion
et afficher le vecteur r'esultat. Exemple de trace produite par un tel programme :
Le vecteur non tri'e
27 24 76 88 93 29 10 36 85 59 99 12 17 77 47 35 73 15 47 21
Le vecteur tri'e
10 12 15 17 21 24 27 29 35 36 47 47 59 73 76 77 85 88 93 99
Pour tirer les valeurs au hasard on utilisera les services de la fonction random() de la
classe Math (Math.random() retourne un double tir'e au hasard dans l'intervalle [0..1]).