Tri à bulles

book
date_range
comment0 commentaire
remove_red_eye12476 vues

En programmation, il est souvent nécessaire de faire un tri dans un tableau pour classer les individus par âge, pour comparer des élements, ... 

Il existe une multitude d'algorithme de tri et on peut bien évidemment en créer un particulier si l'on souhaite classer des résultats suivant un agencement non habituel comme par exemple répartir des joueurs afin que les deux équipes aient un niveau comparable. 

 

Tri à Bulles 


     Aujourd'hui nous allons regarder un algorithme appelé le tri à bulles, son but est de faire remonter progressivement les plus grands éléments afin d'obtenir un ordre croissant. (on pourra très bien le faire décroissant). Autant être clair tout de suite, si vous souhaitez trier un grand nombre de valeurs, ce n'est pas l'algorithme qu'il faudra utiliser puisqu'il n'est absolument pas optimisé et va donc aller très lentement (en moyenne sa complexité est n est le nombre d'élément). 

 

Pourquoi étudier celui ci alors ? 

     Il présente l'avantage d'être simple à comprendre pour une première approche, et d'apporter une première idée de la façon de raisonner, de plus on peut trouver que cet algorithme est "esthétique" dans le sens où l'on peut si on réalise un affichage à chaque étape assisté à la remontée des valeurs comme la remontée des plus grosses bulles dans une casserole. 

 

 Création du fichier


     Commençons par créer un fichier que nous appellerons tribulles.java et ajoutons la méthode main classique. 

 

public class tribulles{
	public static void main (String [ ] args) {		

	}
}
  •      Plutôt que de tout écrire dans la méthode main, nous allons directement créer des fonctions qui seront appelées par la méthode main. 
  •     Pour réaliser un tri nous avons besoin de permuter des valeurs, nous allons donc créer une fonction de permutation.

 

 Fonction de permutation



public static void permuter(int tableau[], int i, int j){
	
	int temp;

	temp = tableau;
	tableau = tableau[j];
	tableau[j] = temp; 
	}

 

  1.  La variable temp garde en mémoire la valeur de la première variable i
  2.  On attribue à la première variable i la valeur de la deuxième variable j.
  3. On attribue à la deuxième variable j, la valeur de la variable temp qui correspond à la première variable i initiale

 

 

  •       Cette fonction permuter prend en paramètres un tableau (dans notre cas d'entiers), ainsi que les indices des éléments du tableau à permuter : permuter(int tableau[], int i, int j)

 

  •      Nous aurons également besoin d'une fonction qui affichera les tableau (avant et après le tri), pour cela on peut utiliser un bel affichage. Présentement c'est la fonction qui réalise le tri qui nous importe nous nous contenterons donc d'un affichage sur une ligne des valeurs. 

 

Fonction d'affichage



public static void affichage(int[]tabVal){
	int ind;
		for (ind=0; ind<N;ind++){
			System.out.print(tabVal[ind]+" ");
			
		}
		System.out.println();
	}

 

  •       Cette fonction prend en valeur le tableau à trier et d'afficher du premier au dernier élément du tableau par l'intermédiaire d'une boucle for. Il est important de se rappeler que le premier indice du tableau est 0 donc on parcourt le tableau de la position 0 à la position (nombre_elements)-1

 

   =>  Interessons nous maintenant au coeur du problème le tri. 

 

Algorithme de tri



public static void triBulles(int[]tabVal){
		int fin,ind;
		fin=N-1;
		boolean permut=true;
		
		do {
			
		permut=false;
			
			for(ind=0;ind<fin;ind++){
			
				if (tabVal[ind]>tabVal[ind+1]){
				permuter(tabVal,ind,ind+1);
				permut=true;
				}
			}
		fin=fin-1;
		}
		while((permut==true)&&(fin>=1));
		

	}
  •      Cette fonction prend le tableau à trier en paramètre. On utilise une boucle do ... while, c'est à dire Faire les permutations Tant que le tableau n'est pas trié. 

 

Pour cela on déclare deux entiers et un booléen

- ind est la variable entière qui sert d'indice pour parcourir le tableau. 

- fin est la variable entière qui indique jusqu'où l'algorithme doit se dérouler. A la première étape, fin est à la dernière position du tableau, à l'étape deux, on sait que la plus grande valeur occupe la dernière position donc on cherche la deuxième plus grand valeur qu'on placera en position fin-1 et ainsi de suite. 

- permut est un booleen qui vérifie s'il y a encore des permutations à effectuer. 

 

  •      Il ne nous reste plus qu'à appeler les fonctions que nous venons de créer dans la méthode main. J'ai crée une constante qui me sert à la fois à définir la taille du tableau et à indiquer qu'elles sont les valeurs que peuvent prendre les cases du tableau, vous pouvez tout à fait en crée deux, ou demander à l'utilisateur de choisir quelles valeurs peuvent prendre les cases du tableau. 

 

Appel des fonctions



public class tribulles{
	public static int N=10;
	public static void main (String [ ] args) {		
		int []tabVal;
		int ind;
			tabVal=new int [N];
		
		for (ind=0; ind<N;ind++){
			tabVal[ind]=(int)(Math.random()*N+1);
			
		}
		affichage(tabVal);
		triBulles(tabVal);
		affichage(tabVal);
	}

 

Remarque :  Pour cet exemple, nous avons rempli le tableau en utilisant la fonction Math.random qui génère des nombres "aléatoires".

Articles similaires

Commentaires

Aucun commentaire

Ajouter un commentaire

Vous ne disposez pas les autorisations nécessaires pour poster un commentaire.