Correction du TP n°6
Implanter en Java la méthode de tri à bulle appliquée aux tableaux d'entiers.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2006 */
import java.io.*;
public class TriABulle {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction d'affichage de tous les entiers contenus */
/* dans un tableau d'entiers */
public static void affichageTableau(int [] t) {
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ )
System.out.println(t[i]);
}
/* Fonction d'initialisation de tous les entiers */
/* contenus dans un tableau d'entiers */
/* avec une valeur tiree au sort entre 0 et max inclus */
public static void initialisationTableau(int [] t,int max) {
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ ) {
/* Initialisation de t[i] avec un entier tire */
/* au hasard entre 0.0 (inclu) et max+1 (exclu) */
t[i] =(int) ((max+1)*Math.random()); }
}
/* Fonction de recherche de l'indice de la valeur */
/* minimum d'un tableau pour les seules valeurs */
/* allant de l'indice deb a l'indice fin inclus */
public static int indiceMinimum(int [] t,int deb,int fin) {
/* Declaration et initialisation a t[deb] de la variable */
/* de stockage de l'indice recherche */
int imin = deb;
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = deb+1 ; i <= fin ; i++ )
/* Si la valeur d'indice i est plus petite que la valeur */
/* d'indice imin */
if ( t[i] < t[imin] )
imin = i;
return(imin);
}
/* Fonction de tri a bulle d'un tableau d'entiers */
public static void triABulle(int [] t) {
/* Definition et initialisation a vrai d'un booleen */
/* pour indiquer qu'une permutation a eu lieu lors d'un */
/* parcours a la recherche de permutations a realiser */
boolean permutation = true;
/* Definition est initialisation de la variable entiere */
/* qui indique l'indice du prochain maximum a envoyer */
/* en bout de tableau par permutations successives */
int limite = t.length-1;
int i;
int val;
/* Tant qu'au moins une permutation a eu lieu au cours */
/* de la passe precedente */
while ( permutation ) {
/* Pour l'instant aucune permutation n'a eu lieu au cours */
/* de cette passe */
permutation = false;
/* Parcours de t a la recherche de permutations pour tous */
/* les couples de valeurs d'indice i et i+1 pour i variant */
/* de 0 a limite-1 */
for ( i = 0 ; i < limite ; i++ ) {
/* Si une permutation doit etre realisee */
if ( t[i] > t[i+1] ) {
/* Permutation */
val = t[i];
t[i] = t[i+1];
t[i+1] = val;
/* Le booleen permutation passe a vrai pour indiquer */
/* qu'un moins une permutation a eu lieu au cours */
/* de cette passe */
permutation = true; } }
/* Un nouveau maximum a ete "pousse" a sa place */
/* -> La limite de recherche est decrementee de 1 */
limite--; }
}
/* Fonction principale */
public static void main(String [] args) throws IOException {
int n;
/* Lecture clavier de l'indice de debut de recherche */
System.out.println("Taille du tableau:");
n = Integer.valueOf(flux.readLine()).intValue();
/* Definition et allocation d'un tableau de 10 entiers */
/* tires au sort entre 0 et 5 */
int [] tab = new int[n];
initialisationTableau(tab,100);
System.out.println("Le tableau contient les valeurs suivantes:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
System.out.println();
/* Appel a la fonction de tri a bulle */
triABulle(tab);
System.out.println("Le tableau trie est:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
}
}
Implanter en Java et tester une fonction permettant de fusionner deux tableaux d'entiers triés par ordre croissant en un seul tableau trié par ordre croissant.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Mars 2006 */
import java.io.*;
public class FusionTableauxTries {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction de fusion de deux tableaux d'entiers tries */
/* en un tableau d'entiers tries */
/* t1,t2 : tableaux d'entiers tries */
/* Resultat fonction : Tableau d'entiers trie */
public static int [] fusion(int [] t1,int [] t2) {
/* Calcul des tailles des tableaux t1 et t2 */
int n1 = t1.length;
int n2 = t2.length;
/* Creation d'un tableau de taille suffisante pour contenir */
/* toutes les valeurs de t1 et t2 : (n1+n2) valeurs */
int [] t = new int[n1+n2];
/* Définition et initialisation a 0 de deux variables */
/* compteur (i1 et i2) pour stocker le nombre de valeurs */
/* de t1 et le nombre de valeurs de t2 qui ont deja */
/* ete placees dans t */
int i1 = 0;
int i2 = 0;
/* Pour les n1+n2 valeurs a placer dans t */
for ( int i = 0 ; i < n1+n2 ; i++ ) {
/* Si toutes les valeurs de t1 sont deja dans t, */
/* la valeur a placer dans t est la premiere valeur */
/* de t2 non encore placee dans t */
if ( i1 == n1 ) {
t[i] = t2[i2];
i2++; }
else
/* Sinon, si toutes les valeurs de t2 sont deja dans t, */
/* la valeur a placer dans t est la premiere valeur */
/* de t1 non encore placee dans t */
if ( i2 == n2 ) {
t[i] = t1[i1];
i1++; }
else
/* Sinon, si la premiere valeur de t1 non placee dans t */
/* est plus petite que la premiere valeur de t2 non placee */
/* dans t, alors c'est la valeur de t1 qui va dans t */
if ( t1[i1] < t2[i2] ) {
t[i] = t1[i1];
i1++; }
else {
/* Sinon, c'est la valeur de t2 qui va dans t */
t[i] = t2[i2];
i2++; } }
/* Resultat fonction : le tableau t ainsi cree et rempli */
return(t);
}
/* Fonction de creation d'un tableau trie d'entiers */
/* tires au hasard */
/* taille : nombre d'entiers du tableau */
public static int [] tableauTrie(int taille) {
/* Creation d'un tableau de taille entiers */
int [] t = new int[taille];
/* Initialisation de t[0] avec un entier tire au sort */
/* dans l'intervalle [0,4] */
t[0] =(int) (Math.random()*5);
/* Pour toutes les valeurs restant a initialiser */
for ( int i = 1 ; i < t.length ; i++ )
/* La valeur d'indice i est affectee avec la valeur */
/* d'indice i-1 a laquelle on ajoute une valeur */
/* tiree au sort dans l'intervalle [0,4] */
t[i] = t[i-1] + (int) (Math.random()*5);
/* Resultat fonction : le tableau t ainsi initialise */
return(t);
}
/* Fonction d'affichage d'un tableau d'entiers */
/* t : tableau dont les valeurs doivent etre affichees */
public static void afficheTableau(int [] t) {
int i;
for ( i = 0 ; i < t.length ; i++ )
System.out.print(t[i]+" ");
System.out.println();
}
/* Fonction principale */
public static void main(String [] args) throws IOException {
/* Lecture au clavier des donnees initiales */
System.out.print("Taille du premier tableau : ");
int n1 = Integer.valueOf(flux.readLine()).intValue();
System.out.print("Taille du second tableau : ");
int n2 = Integer.valueOf(flux.readLine()).intValue();
/* Generation des tableaux a fusionner */
int [] t1 = tableauTrie(n1);
int [] t2 = tableauTrie(n2);
/* Affichage des tableaux a fusionner */
System.out.println("Premier tableau :");
afficheTableau(t1);
System.out.println("Second tableau :");
afficheTableau(t2);
/* Fusion des tableaux */
int [] t = fusion(t1,t2);
/* Affichage du tableau issu de la fusion */
System.out.println("Tableau fusionne :");
afficheTableau(t);
}
}
Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr
