Correction du TP n°5

Exercice 1

Implanter en Java la méthode de tri par sélection appliquée aux tableaux d'entiers.

/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2006 */
import java.io.*;
public class TriSelection {
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 par selection d'un tableau d'entiers */
public static void triSelection(int [] t) {
int indmin;
int i;
int val;
/* Pour les t.length-1 passes de l'algorithme de tri */
for ( i = 0 ; i < t.length-1 ; i++ ) {
/* Recherche de l'indice de la valeur minimale de t */
/* pour les valeurs d'indice i a t.length-1 */
indmin = indiceMinimum(t,i,t.length-1);
/* Permutation si necessaire */
if ( i != indmin ) {
val = t[i];
t[i] = t[indmin];
t[indmin] = val; } }
}
/* 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 par selection */
triSelection(tab);
System.out.println("Le tableau trie est:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
}
}

TriSelection.java

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr