Exchange ou le tri des bulles

Bulle tri méthode est basée sur deux comparaisons successives d'éléments consécutifs et faire un échange entre les éléments jusqu'à qui sont ordonnés.

Supposons que le vecteur indiqué dans le tableau suivant, pour effectuer la gestion ont suivi ces paso :

• Que compare les deux premiers éléments, si la seconde est plus élevée que la première, ils sont pas comme ils sont, mais si la première est la plus importante, sont des éléments échangés.
• Est alors comparé au second élément avec le troisième en appliquant les mêmes critères que l'étape précédente.
• De cette façon est répété l'opération en comparaison avec tous les éléments qui forment le vecteur. Lorsqu'il atteint le dernier élément a été l'élément qui a la valeur la plus élevée, et cela a été située à l'extrémité du vecteur.
• Pour trouver que le deuxième élément est répété la gestion des opérations de tous les éléments du tableau sauf le dernier.
• Réaffirmant le processus décrit, le vecteur d'être ordonnée lorsqu'on compare les seuls les deux premiers éléments.

Première gestion.

Exemple de gestion par bulle pour trouver le premier élément.

	vecteur	comparaison 1ère	2ème comparaison	3e comparaison	4e comparaison	5e comparaison
V [1]	3	3	3	3	3	3
V [2]	34	34	1	1	1	1
V [3]	1	1	34	34	34	34
v [4]	53	53	53	53	15	15
V [5]	15	15	15	15	53	6
V [6]	6	6	6	6	6	53

des processus de gestion exprimé en pseudocóJe dis structuré e:

 de j. ← 1 à n-1 faire si élément [j] > élément [j + 1] puis intercambiar(elemento[j],_elemento[j+1]) fin_si fin_desde

pour le processus d'échange d'éléments a utiliser une variable auxiliaire de la forma suivante :

 aux ← V [j] V [j] ← V [j + 1] V [j + 1] ← aux

Deuxième gestion.

	vecteur	1ère gestion	1ère comparaison	la comparaison de la 2e	3e comparaison	4e comparaison
V [1]	3	3	1	1	1	1
V [2]	34	1	3	3	3	3
V [3]	1	34	34	34	15	15
V [4]	53	15	15	15	34	6
V [5]	15	6	6	6	6	34
V [6]	6	53	53	53	53	53

Après l'ordination deuxième les deux éléments de vecteur plus importantes ont été trouvés et qu'ils ont eux-mêmes placés à la fin de la même.

Algorithme de bulle.

Est de généraliser le processus de gestion obtient le pseudo-code suivant structuré pour l'algorithme de bulle

i - les ordinations variables <br/> j - comparaisons variables <br/> n - nombre d'éléments dans le vecteur (c représente le plus gros index)

 algorithme bulles maison / / ordinations puisque je ← 1 à n-1  / / comparaisons de j ← 1 place NI faire si élément [j] > élément [j + 1] puis / / Exchange aux éléments ← V [j] V [j] ← V [j + 1] V [j + 1] ← aux fin_si fin_desde fin_desde fin

exemple en c:

 v [] int = {3, 34, 1, 53, 15, 6}; int j, i, aux ;

/ / Gestion pour (i = 0; _i < 5; _i ++) {/ / comparaisons pour (j = 0; _j < 5-i; _j ++) {/ / Exchange élément si (v [j] _ > _v[j+1]) {aux = v [j];}}}
		v [j] = v [j + 1] ;
		v [j + 1] = aux ;
		{}}

réitérant dans le tri get triés vectoriel comme le montre le tabla suivante :

	vecteur	1ère gestion	gestion 2e	gestion 3e	gestion 4e	gestion 5e
V [1]	3	3	1	1	1 <br/>	1
V [2]	34	1	3	3	3	3
V [3]	1	34	15	6	6	6
V [4]	53	15	6	15	15	15
V [5]	15	6	34	34	34	34
V [6]	6	53	53	53	53	53

Méthode de gestion de la bulle améliorée.

Si vous regardez le tableau de sortes que nous remarquons que le vecteur a ordonné à la troisième gestion, inutile de faire de la gestion des quatrième et cinquième, toutefois analysés bulle algorithme effectue toutes les comparaisons de tri jusqu'à (n-1). Vous pouvez détecter que le vecteur est ordonné et interrompre les ordinations, améliorant ainsi les performances de l'algorithme. Quand est une gestion si toutes les comparaisons il y a eu un échange d'éléments, c'est parce que le vecteur est ordonné. Un indicateur, drapeau ou une variable booléenne peut être utilisé pour détecter la fin de la gestion

L'algorithme suivant montre un de la méthode des versions optimisées de tri bulle.

i - les ordinations variables <br/> j - comparaisons variables <br/> n - nombre d'éléments dans le vecteur (c représente le plus gros index) <br/> ord - indicateur Variable du vecteur trié

 algorithme Burbuja2 domicile / / ordinations je ← 1 / / démarrer les ordinations ord ← 0 / / démarrer indicateur du vecteur ord tandis que l'ordre = 0 ord faire ← 1 / / comparaisons de j ← 1 à n-je faire si élément [j] > élément [j + 1] puis / / Exchange aux éléments ← V [j] V [j] ← V [j + 1] V [j + 1] ← aux ord ← 0 fin_si fin_desde i ← k fin_mientras fin

exemple dans C:

 int v [] = {3, 34, 1, 53, 15, 6}; int j, aux ; int i = 0; bool ord = false ;

/ / Ordinations while(!ord) {/ / comparaisons ord = true;}
	pour (j = 0; j < 5-i; j ++) {si (v [j] > v[j+1]) {/ / Exchange aux éléments = v [j];}}
			v [j] = v [j + 1] ;
			v [j + 1] = aux ;
			Ord = false ;	{{/ / Indicateur de triés vecteur}} i ++ ;
}

Exemple en C++ Builder :

 / /-# include <vcl.h> # include <iostream.h> # include <conio.h> # pragma hdrstop / /-# pragma argsused int main(int_argc,_char*_argv[]) {/ / variable int v [] = {3, 34, 1, 53, 15, 6}; int j, aux ; int i = 0; bool ord = false;}

/ / Afficher le vecteur (int_n = 0; _n < 6; _n ++) {cout << v [n] << "";}

/ / Ordinations while(!ord) {/ / comparaisons ord = true;}
	pour (j = 0; j < 5-i; j ++) {si (v [j] > v[j+1]) {/ / Exchange aux éléments = v [j];}}
			v [j] = v [j + 1] ;
			v [j + 1] = aux ;
			Ord = false ;	{{/ / Indicateur de triés vecteur}} i ++ ;
} / / Afficher le tableau a ordonné le cout << endl ;
pour (int_n = 0; _n < 6; _n ++) {cout << v [n] << "";}

getch() ;
retour 0 ;
} / /-

Nombreux auteurs critiquent la méthode de commande pour la bulle en raison de sa faible rendement et sa signification desmerecida, bien que je partage ce point de vue, est un système très simple qui s'adapte parfaitement à son atelier dans les centres de formation.

Autres méthodes de gestion comme sélection ou insertion donne de meilleurs résultats, des systèmes de gestion rapide (quicksort), Shell et fusion sont les plus efficaces, fournissant certains spectaculaire renvoie lorsqu'il s'agit d'un ordre de vecteurs de grandes dimensions.