Méthode du tri à bulles
(Tri par échange ou transposition)
Énoncé
Écrire une marche à suivre qui permet de trier un tableau T
à N éléments en ordre décroissant. (N, T sont des données)

I) Préanalyse :
Données : 
- Le nombre d'éléments de T  (N=6);
- Un tableau T à N éléments de types entiers ;
T 17 12 50 10 33 15 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

Résultat :
Un tableau trié

T 50 33 17 15 12 10 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

Les étapes de résolution :
Le principe de ces algorithmes est d'échanger des éléments deux par deux, en les réordonnant.
Si nous considérons deux clés, C1 et C2, telles que C1 < C2, en effectuant un tri
par ordre décroissant, nous échangerons C1 et C2. Si par contre, les deux clés dans
le bon ordre, elle seront laissées à leur place. La répétition de ce processus à l'ensemble
des clés permet d'obtenir un nouveau classement, plus proche du classement final.
Bien sûr, dans ce cas, la répétition de plusieurs passages sur l'ensemble des données
est nécessaire pour l'obtention d'un tri complet.
Cette méthode est appelée le tri à bulles, car les éléments mal classés remontent dans

la liste comme des bulles à la surface d'un liquide.

Passage 1 : echange = Faux

T 17 12 50 10 33 15 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10
T 17 50 12 33 15 10 ? ? ? ?

..................echange = Vrai

Passage 2 : echange = Faux

T 17 50 12 33 15 10 ? ? ? ?
1
1
2
3
4
5
N=6
7
8
9
NMAX=10
T 50 17 33 15 12 10 ? ? ? ?

..................echange = Vrai

Passage 3 : echange = Faux

T 50 17 33 15 12 10 ? ? ? ?
1
1
2
3
4
5
N=6
7
8
9
NMAX=10
T 50 33 17 15 12 10 ? ? ? ?

echange = Vrai

Passage 4: echange = Faux

T 50 33 17 15 12 10 ? ? ? ?
1
1
2
3
4
5
N=6
7
8
9
NMAX=10
T 50 33 17 15 12 10 ? ? ? ?

echange = Faux

d'où le tableau T est trié

..............................................................................................Les noms des modules (sous-programmes)

Saisir (Lire) le nombre d'éléments de T .............................................. Lecture(N)
Remplir le tableau T par N éléments .................................................. Remplir(N,T)
Trier le tab en ordre décroissant ........................................................ Tri_bulles(N,T)
Permuter le contenu de deux variables................................................ Permut(A,B)
Afficher le tableau T après le tri..........................................................Affiche(N,T)

II) Analyses & Algorithmes :

1) Analyse du programme principal

Nom : Tri_methode_a_bulles
S.
LDE
O.U.

4

1

3

2

5

Résultat : Affiche ( N , Tr )

N = Lecture( N )

Tr= Tri_bulles ( N , Ti)

Ti = Remplir ( N , Ti )

Fin Tri_methode_a_bulles

N, Tr, Ti

Lecture

Tri_bulles

Remplir

Affiche

Tableau de déclaration des objets :

O.U.
Nature/Type
Rôle
N
Var/Entier
 Le nombre d'éléments du tableau T
Ti
Var/Tab
 Tableau des valeurs à l'état initial
Tr
Var/Tab
 Tableau trié
Lecture
Procédure
 Lecture de N
Remplir
Procédure
 Remplit le tableau T par des valeurs
Tri_bulles
Procédure
 Trie le tableau T en ordre décroissant
Affiche
Procédure
 Affiche les valeurs du tableau après insertion

Nouveau Type ................Tab = Tableau [1..NMax] d'entier

NMax est une constante égale à 10

Algorithme du programme principal :

0- Début Tri_methode_a_bulles
1- Lecture( N )
2- Remplir ( N , T )
3- Tri_bulles ( N , P )
4- Affiche ( N , T )
5- Fin Tri_methode_a_bulles

2) Analyse de la procédure Lecture

DEF PROC Lecture (Var N : Entier)
S.
LDE
O.U.

 

 Résultat : N
1
 N= [ ] Répeter

N=donner

Jusqu'à N dans [ 1 .. Nmax ]
2
 Fin Lecture 
Algorithme de la procédure Lecture :
0- DEF PROC Lecture (Var N : Entier)
1- Répeter
 
..........Lire( N )
  Jusqu'à N dans [ 1 .. Nmax ]
2- Fin Lecture

3) Analyse de la procédure Remplir

DEF PROC Remplir ( N : Entier ; Var T: Tab )
S.
LDE
O.U.

 

 Résultat : T

I

 
1
 T= [ ] Pour I de 1 à N Répéter

...................T[I]=donnée

..........Fin Pour

I = Compteur
2

Fin Remplir

Tableau de déclaration des objets :
O.U.
Code
Nature/Type
Rôle
I
I
Var/Entier
 Compteur 
Algorithme de la procédure Remplir :
0- DEF PROC Remplir ( N : Entier ; Var T : Tab )
1- Pour I de 1 à N Répéter
 
.......... Lire( T[I] )
 

Fin Pour
2- Fin Remplir

4) Analyse de la procédure Tri_bulles

DEF PROC Tri_bulles ( N : Entier ; Var T : Tab )
S.
LDE
O.U.

 

 Résultat : T

I

echange
1
 T= [ ] Repeter
..............[echange <-- Faux] Pour I de 1 à N-1 Répéter
................................................[ ] Si T[I] < T[I+1]
............................................................Alors
...................................................................Permut ( T[ppm], T[I] )
...................................................................echange <-- Vrai
............................................................FinSi

............................................ .Fin Pour

..........Jusqu'a echange = Vrai

I = Compteur
2

Fin Tri_bulles

Tableau de déclaration des objets :
O.U.
Nature/Type
Rôle
I
Var/Entier
 Compteur
echange
Var/Booleen

Contiendra faux comme une valeur initiale, vrai en cas d'une permutation
Tr
Var/Tab
 Tableau trié
Permut
Procédure
 Permute le contenu de deux variables 
Algorithme de la Procédure Tri_bulles :
0-

DEF PROC Tri_bulles ( N : Entier ; Var T : Tab )
1
 Repeter
  .............echange <-- Faux
.............. Pour I de 1 à N-1 Répéter
...........................Si T[I] < T[I+1]
.........................................Alors
................................................ Permut ( T[ppm], T[I] )
.................................................echange <-- Vrai
  ............................FinSi
 

.............. Fin Pour

Jusqu'a echange = Faux
2

Fin Tri_bulles

5) Analyse de la procédure Permut

DEF PROC Permut ( Var A, B : Entier )
S.
LDE
O.U.

Résultats : Af, Bf
2
 A <-- B
Aux
3

B <-- Aux
1

Aux <-- A
4

Fin Permut

Tableau de déclaration des objets :

O.U.
Nature/Type
Rôle
Aux
Var/Entier
 Variable auxiliaire nécessaire à la permutation

Algorithme de la procédure Permut :

0- DEF PROC Permut ( Var A, B : Entier )
1- Aux <-- A
2-
A <-- B
3-

B <-- Aux
4- Fin Permut

6) Analyse de la procédure Affiche :

DEF PROC Affiche ( N : Entier ; T : Tab )
S.
LDE
O.U.
1
 Résultat :

 

I

 
....... [ ] Pour I de 1 a N Répéter

...................Ecrire ( T[I] )

..........Fin Pour

I = Compteur
2

Fin Affiche

Tableau de déclaration des objets :
O.U.
Nature/Type
Rôle
I
Var/Entier
 Compteur 
Algorithme de la procédure Affiche :
0- DEF PROC Affiche ( N : Entier ; T : Tab )
1- Pour I de 1 à N Répéter
 
.......... Ecrire ( T[I] )
  Fin Pour
2- Fin Affiche

III) Traduction en Turbo Pascal :

Program Tri_methode_a_bulles ;

Const NMax = 10 ;

Type Tab = ARRAY [1..Nmax] Of Integer ;

Var T : Tab ;

.......N : Integer ;
{---------------------------------------------------}

PROCEDURE Lecture ( Var N : Integer ) ;

Begin

.......Repeat

..............Readln ( N ) ;

.......Until N in [ 1 .. Nmax ] ;

End ;
{---------------------------------------------------}

PROCEDURE Remplir ( N : Integer ; Var T : Tab ) ;

Var I : Integer ;

Begin

......For I : = 1 To N Do

.......... Readln ( T[I] ) ;

End ;
{---------------------------------------------------}

PROCEDURE Permut ( Var A, B : Integer ) ;
Var Aux : Integer;

Begin

.......Aux : = A ;

.......A : = B ;

.......B : = Aux ;

End ;
{---------------------------------------------------}

PROCEDURE Tri_bulles ( N : Integer ; Var T : Tab );

Var I, ppm : Integer ;

Begin

.............. Repeat

........................... echange : = False;

.............. .............. For I : = 1 to N-1 Do

........................