Correction du TP n°5 et du TP n°6
Tri par selection.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TriSelection {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction de recherche de l'indice du plus petit */
/* element d'un tableau d'entiers */
/* t : tableau ou effectuer la recherche */
/* deb : indice a partir duquel commencer la recherche */
/* fin : indice jusqu'auquel effectuer la recherche */
public static int indiceDuMinimum(int [] t,int deb,int fin) {
int ind = deb;
for ( int i = deb+1 ; i <= fin ; i++ )
if ( t[i] < t[ind] )
ind = i;
return(ind);
}
/* Fonction de tri par selection */
/* t : tableau a trier */
public static void triSelection(int [] t) {
/* Pour tous les indices deb jusqu'a l'anvant dernier */
for ( int deb = 0 ; deb < t.length-1 ; deb++ ) {
/* Calcul de l'indice i du minimum */
/* de deb jusqu'a fin du tableau */
int i = indiceDuMinimum(t,deb,t.length-1);
/* Permutation des elements d'indice i et deb */
int v = t[deb];
t[deb] = t[i];
t[i] = v; }
}
/* Fonction de creation d'un tableau d'entiers */
/* tires au hasard */
/* taille : nombre d'entiers du tableau */
/* max : valeur maximale des entiers tires au sort */
public static int [] initTableau(int taille,int max) {
int [] t = new int[taille];
for ( int i = 0 ; i < t.length ; i++ )
t[i] =(int) (Math.random()*(max+1));
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 tableau a generer et a trier : ");
int n = Integer.valueOf(flux.readLine()).intValue();
System.out.print("Valeur maximale des entiers du tableau : ");
int max = Integer.valueOf(flux.readLine()).intValue();
/* Generation du tableau a trier tire au hasard */
int [] t = initTableau(n,max);
/* Affichage du tableau non trie */
System.out.println("Tableau initial :");
afficheTableau(t);
/* Tri du tableau */
triSelection(t);
/* Affichage du tableau trie */
System.out.println("Tableau trie :");
afficheTableau(t);
}
}
Tri à bulle.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TriBulle {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction de tri a bulle */
/* t : tableau a trier */
public static void triBulle(int [] t) {
/* Definition d'un booleen pour indiquer si le tri */
/* est fini (initialise a zero) */
boolean stop = false;
/* Definition d'un compteur pour indiquer le nombre */
/* de cellules deja triees */
int ind = 0;
/* Tant que le tri n'est pas fini */
while ( !stop ) {
/* stop est affecte a vrai pour indiquer que sauf */
/* si au moins une permutation a lieu, le tri sera fini */
stop = true;
/* Boucle de parcours du tableau a la recherche */
/* d'une permutation. Les ind premieres cellules */
/* etant deja triees, la boucle commence a l'indice ind */
for ( int i = 0 ; i < t.length-1-ind ; i++ )
/* Test de l'occurrence d'une permutation */
/* entre i et i+1 */
if ( t[i] > t[i+1] ) {
/* Si une permutation a lieu, le tri ne sera pas fini */
/* a l'issue de la boucle for -> ajustement de stop */
stop = false;
/* Permutation des elements d'indice i et i+1 */
int v = t[i];
t[i] = t[i+1];
t[i+1] = v; }
/* Une cellule de plus est triee */
ind++; }
}
/* Fonction de creation d'un tableau d'entiers */
/* tires au hasard */
/* taille : nombre d'entiers du tableau */
/* max : valeur maximale des entiers tires au sort */
public static int [] initTableau(int taille,int max) {
int [] t = new int[taille];
for ( int i = 0 ; i < t.length ; i++ )
t[i] =(int) (Math.random()*(max+1));
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 tableau a generer et a trier : ");
int n = Integer.valueOf(flux.readLine()).intValue();
System.out.print("Valeur maximale des entiers du tableau : ");
int max = Integer.valueOf(flux.readLine()).intValue();
/* Generation du tableau a trier tire au hasard */
int [] t = initTableau(n,max);
/* Affichage du tableau non trie */
System.out.println("Tableau initial :");
afficheTableau(t);
/* Tri du tableau */
triBulle(t);
/* Affichage du tableau trie */
System.out.println("Tableau trie :");
afficheTableau(t);
}
}
Tri par insertion. Version non optimisée mais plus simple où la recherche de la position d'insertion fournit la position la plus à gauche lorsque plusieurs sont possibles (insertion d'une valeur v dans une liste triée où v est déjà présent une ou plusieurs fois) -> Il y a plus de décalages à faire pour libérer la place nécessaire à l'insertion.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TriInsertion {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction de recherche de la position d'insertion */
/* d'une valeur du tableau a l'interieur du tableau */
/* ind : indice de la valeur dont on calcule */
/* la position d'insertion */
/* t : tableau ou la position d'insertion */
/* est recherchee */
public static int indiceInsertion(int ind,int [] t) {
/* Definition d'une variable entiere de recherche */
/* de la position d'insertion (initialisee a 0) */
int i = 0;
/* La boucle de recherche s'execute tant que la valeur */
/* a l'indice courant est plus petite que la valeur */
/* que l'on souhaite inserer */
/* -> La boucle s'arrete quand on a trouve la premiere */
/* valeur du tableau t superieure ou egale a la valeur */
/* a inserer ou, au pire, sur la valeur elle-meme */
while ( t[i] < t[ind] )
/* L'indice de recherche est incremente de 1 */
i++;
/* Resultat : i */
return(i);
}
/* Fonction d'insertion d'une valeur du tableau */
/* a sa position dans l'ordre de tri */
/* pos : Position d'insertion */
/* t : Tableau ou l'insertion est realisee */
/* src : Indice de la valeur a inserer */
public static void insertion(int pos,int [] t,int src) {
/* Sauvegarde de la valeur a inserer */
int v = t[src];
/* Decalage des valeurs du tableau t pour "faire */
/* une place" a la valeur a inserer */
/* Le decalage est effectue a rebour (de l'indice */
/* final a l'indice d'insertion par pas de -1 */
for ( int i = src ; i > pos ; i-- )
t[i] = t[i-1];
/* Insertion */
t[pos] = v;
}
/* Fonction de tri par insertion */
/* t : tableau a trier */
public static void triInsertion(int [] t) {
/* Pour tous les indices de 1 au dernier indice */
/* du tableau a trier */
for ( int i = 1 ; i < t.length ; i++ ) {
/* Determination de la position d'insertion */
/* de l'element d'indice i dans la partie du tableau */
/* deja triee */
int indice = indiceInsertion(i,t);
/* Si la position d'insertion est differente */
/* de la position actuelle */
if ( indice != i )
/* On realise l'insertion */
insertion(indice,t,i); }
}
/* Fonction de creation d'un tableau d'entiers */
/* tires au hasard */
/* taille : nombre d'entiers du tableau */
/* max : valeur maximale des entiers tires au sort */
public static int [] initTableau(int taille,int max) {
int [] t = new int[taille];
for ( int i = 0 ; i < t.length ; i++ )
t[i] =(int) (Math.random()*(max+1));
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 tableau a generer et a trier : ");
int n = Integer.valueOf(flux.readLine()).intValue();
System.out.print("Valeur maximale des entiers du tableau : ");
int max = Integer.valueOf(flux.readLine()).intValue();
/* Generation du tableau a trier tire au hasard */
int [] t = initTableau(n,max);
/* Affichage du tableau non trie */
System.out.println("Tableau initial :");
afficheTableau(t);
/* Tri du tableau */
triInsertion(t);
/* Affichage du tableau trie */
System.out.println("Tableau trie :");
afficheTableau(t);
}
}
Tri par insertion. Version optimisée mais légèrement plus complexe où la recherche de la position d'insertion fournit la position la plus à droite lorsque plusieurs sont possibles (insertion d'une valeur v dans une liste triée où v est déjà présent une ou plusieurs fois) -> Il y a le minimum de décalages à faire pour libérer la place nécessaire à l'insertion.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TriInsertionBis {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction de recherche de la position d'insertion */
/* d'une valeur du tableau a l'interieur du tableau */
/* ind : indice de la valeur dont on calcule */
/* la position d'insertion */
/* t : tableau ou la position d'insertion */
/* est recherchee */
public static int indiceInsertion(int ind,int [] t) {
/* Definition d'une variable entiere de recherche */
/* de la position d'insertion (initialisee a 0) */
int i = 0;
/* La boucle de recherche s'execute tant que la valeur */
/* a l'indice courant est plus petite ou egale */
/* que la valeur que l'on souhaite inserer et que */
/* l'indice courant est strictment inferieur a l'indice */
/* de la valeur a inserer */
/* -> La boucle s'arrete quand on a trouve la premiere */
/* valeur du tableau t superieure strictement */
/* a la valeur a inserer ou que l'on est a l'indice */
/* de la valeur elle-meme */
while ( ( t[i] <= t[ind] ) && ( i < ind ) )
/* L'indice de recherche est incremente de 1 */
i++;
/* Resultat : i */
return(i);
}
/* Fonction d'insertion d'une valeur du tableau */
/* a sa position dans l'ordre de tri */
/* pos : Position d'insertion */
/* t : Tableau ou l'insertion est realisee */
/* src : Indice de la valeur a inserer */
public static void insertion(int pos,int [] t,int src) {
/* Sauvegarde de la valeur a inserer */
int v = t[src];
/* Decalage des valeurs du tableau t pour "faire */
/* une place" a la valeur a inserer */
/* Le decalage est effectue a rebour (de l'indice */
/* final a l'indice d'insertion par pas de -1 */
for ( int i = src ; i > pos ; i-- )
t[i] = t[i-1];
/* Insertion */
t[pos] = v;
}
/* Fonction de tri par insertion */
/* t : tableau a trier */
public static void triInsertion(int [] t) {
/* Pour tous les indices de 1 au dernier indice */
/* du tableau a trier */
for ( int i = 1 ; i < t.length ; i++ ) {
/* Determination de la position d'insertion */
/* de l'element d'indice i dans la partie du tableau */
/* deja triee */
int indice = indiceInsertion(i,t);
/* Si la position d'insertion est differente */
/* de la position actuelle */
if ( indice != i )
/* On realise l'insertion */
insertion(indice,t,i); }
}
/* Fonction de creation d'un tableau d'entiers */
/* tires au hasard */
/* taille : nombre d'entiers du tableau */
/* max : valeur maximale des entiers tires au sort */
public static int [] initTableau(int taille,int max) {
int [] t = new int[taille];
for ( int i = 0 ; i < t.length ; i++ )
t[i] =(int) (Math.random()*(max+1));
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 tableau a generer et a trier : ");
int n = Integer.valueOf(flux.readLine()).intValue();
System.out.print("Valeur maximale des entiers du tableau : ");
int max = Integer.valueOf(flux.readLine()).intValue();
/* Generation du tableau a trier tire au hasard */
int [] t = initTableau(n,max);
/* Affichage du tableau non trie */
System.out.println("Tableau initial :");
afficheTableau(t);
/* Tri du tableau */
triInsertion(t);
/* Affichage du tableau trie */
System.out.println("Tableau trie :");
afficheTableau(t);
}
}
Fusion de deux tabelaux triés en un tableau trié.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
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
