Deug MASS 2 Année 2000/2001
U.N.S.A.



ALGORITHMIQUE ET STRUCTURES DE DONNEES

TP 7

Tris itératifs et Révisions

1. Tri à bulles

Ecrire une méthode Java implémentant une variante de l'algorithme du tri à bulles étudié en cours et en TD de manière à pouvoir spécifier le sens désiré du tri (croissant ou décroissant), et trier le tableau sur lequel la méthode a été appelée en conséquence.

public void triBulle(int sens)

On prendra par convention :
0=décroissant
1=croissant

2. Drapeau à trois couleurs

1)Ecrire une méthode Java qui implémente l'algorithme du tri à trois couleurs pour un tableau dont les éléments peuvent prendre 3 valeurs quelconques, passées en paramètres de la méthode.

public void drapeau3(int V1, int V2, int V3)

2)Ecrire une autre méthode Java permettant de trier (en utilisant une variante de l'algorithme du drapeau à trois couleurs) un tableau rempli avec des valeurs quelconques de façon à trouver :

• au début du tableau les valeurs supérieures à un nombre B1,
• au centre du tableau les valeurs comprises entre un nombre B2 et B1,
• à la fin du tableau les valeurs supérieures à B2.

Les valeurs B1 et B2 sont passées en paramètres lors de l'appel de la méthode.
Remarque : les éléments de chaque partie n'ont pas besoin d'être triés.

public void drapeau3bis(int B1, int B2)

3. Révisions

3.1 Exercice 1

1)Ecrire une méthode Java qui tire Nb éléments au hasard entre V1 et V2 et affiche les valeurs obtenues par ordre croissant.

public void ex1(int Nb, int V1, int V2)

Indications : Utiliser un tableau de V2-V1+1 cases pour stocker les tirages au fur et à mesure. Dans la première case, stocker le nombre de fois où le nombre V1 est tiré, dans la seconde le nombre de fois où V1+1 est tiré, etc. Puis parcourir le tableau et afficher le nombre autant de fois qu'il est indiqué dans la case correspondante du tableau.
2)Quelles sont les modifications à apporter de façon à ce que le tableau qui était précédemment affiché soit renvoyé à la méthode appelante ?

3.2 Exercice 2

Ecrire une méthode Java calculant les uns après les autres les N nombres premiers en partant de la valeur V et les range par ordre décroissant dans un tableau de taille N.

public Tableau ex2(int N, int V)

3.3 Exercice 3

Ecrire une méthode Java permettant, à partir d'un tableau T1 de N nombres, de construire deux tableaux T2 et T3:

• T2 contenant tous les éléments pairs de T1,
• T3 contenant tous les éléments impairs de T1.

La méthode doit ensuite trier en ordre croissant T2 par la méthode du tri par insertion et T3 par la méthode du tri à bulles. Et enfin, la méthode doit fusionner les tableaux T2 et T3 afin d'obtenir un tableau trié par ordre croissant.
Remarque : le tableau ainsi obtenu n'est autre que le tableau initial trié par ordre croissant.

public void ex3()