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



ALGORITHMIQUE ET STRUCTURES DE DONNEES

TP 5

Tris itératifs

1. Tris

1.1 Tri par insertion

Ecrire méthode JAVA de tri par insertion en ordre décroissant.

2. Tri sur un tableau d'entier

Le but de cet exercice est d'ecrire une méthode JAVA pour trier de manière croissante un tableau d'entier dont on connait l'element minimal et l'element maximal. Il s'agit d'utiliser un tableau intermédiaire pour stocker de manière ordonnée le nombre d'occurences de chaque élément du tableau initial, puis construire le tableau final qui sera ordonné.

Notre programme sera donc composé de deux phases, une compression et une decompression.

2.1 Compression

On commence par trouver la valeur minimale (min) et la valeur maximale (max) du tableau à trier. On construit ensuite un tableau intermédiaire de taille max-min+1.
Dans ce tableau, on stockera le nombre d'occurences de chaque valeur du tableau initial. Ce nombre sera inséré dans la case dont l'indice correspond à la valeur de l'élément.
Par exemple, si le tableau a trier comprend une fois le chiffre 5, alors la cinquième case du tableau intermédiaire aura la valeur 1. Si il y a 3 fois le chiffre 4, alors la 4eme case du tableau intermédiaire aura la valeur 3.

2.2 Décompression

Une fois le tableau intermédaire obtenu, nous pouvons construire le tableau final. Il suffit pour cela de regarder chaque case du tableau intermédiaire. Si la ieme case contient la valeur 3, alors il faudra mettre dans le tableau final 3 fois la valeur i+min.

2.3 Implémentation

1) Ajouter a la classe TriTableau les méthodes

public int elementMin()
public int elementMax()

qui retournent respectivement le plus petit et le plus grand des éléments du tableau.

2) Créer la méthode

public TriTableau compresse(int min, int max)

3) Créer la méthode

public TriTableau decompresse(int taille, int min)

2.4 Algorithmes

2.4.1 compresse(int min, int max)

tabloIntermediaire = nouveau TriTableau[max-min];
tabloIntermediaire.remplitAvecValeurZero();
Pour i = 0 a taille Faire
tabloIntermediaire[contenu[i]-min]+=1;

FinPour
retourne tabloIntermediaire

2.4.2 decompresse(int ta, int min)

tabloFinal = nouveauTriTableau(ta);
int index=0;
pour i=0 a taille Faire
pour j=0 a contenu[i] Faire
tabloFinal.setValeur(index, min+i)
index++;
FinPour
FinPour
retourne tabloFinal

2.5 Exemple

public static void main(String args[]) {
......
t=new TriTableau(10,10);
System.out.println( "Un nouveau tableau " + t);
TriTableau tabloCompresse = t.compresse();
System.out.println( "Le tableau compresse est " + tabloCompresse);
TriTableau tabloDecompresse = tabloCompresse.decompresse(t.taille, min);
System.out.println( "Le tableau trie est " + tabloDecompresse);
}

donnera comme execution

Un nouveau tableau [4,1,8,4,2,9,10,2,10,5]
Le tableau compresse est [1,2,0,2,1,0,0,1,1,2]
Le tableau trie est [1,2,2,4,4,5,8,9,10,10]