Le tri à bulle
Le principe du tri à bulles (bubble sort ou sinking sort ) est de comparer deux à deux les éléments e1 et e2 consécutifs d'un tableau et d'effecteur une permutation si e1 > e2 . On continue de trier jusqu'à ce qu'il n'y ait plus de permutation.
L'animation ci-après détaille le fonctionnement du tri bulle :
Démonstration du tri à bulles
PROCEDURE tri_bulle ( TABLEAU a[ 1 : n] )
passage ← 0
REPETER
permut ← FAUX
POUR i VARIANT DE 1 A n - 1 - passage FAIRE
SI a[ i] > a[ i+ 1 ] ALORS
echanger a[ i] ET a[ i+ 1 ]
permut ← VRAI
FIN SI
FIN POUR
passage ← passage + 1
TANT QUE permut = VRAI
let tri_bulle tableau =
let passage= ref 1 and permutation = ref true in
while ( ! permutation = true ) do
permutation := false ;
passage := ! passage + 1 ;
for en_cours
= 0 to ( Array . length tableau
) - ! passage
do if tableau. ( en_cours) > tableau. ( en_cours + 1 ) then
begin
(* On echange les deux elements *)
permutation := true ;
let temp = tableau. ( en_cours) in
begin
tableau. ( en_cours) <- tableau. ( en_cours + 1 ) ;
tableau. ( en_cours + 1 ) <- temp;
end
end
done ;
done ;
tableau;;
type tab = array [ 1 ..20 ] of integer ;
procedure tri_bulle( var tableau : tab) ;
var permutation : boolean ;
en_cours : integer ;
temp : integer ;
passage : integer ;
begin
passage := 1 ;
REPEAT
permutation := false ;
for en_cours := 1 to 20 - passage do
begin
if ( tableau[ en_cours] > tableau[ en_cours + 1 ] ) then
begin
{ on échange les deux éléments }
temp := tableau[ en_cours] ;
tableau[ en_cours] := tableau[ en_cours + 1 ] ;
tableau[ en_cours 1 ] := temp;
permutation := true ;
end ;
end ;
passage := passage 1 ;
UNTIL ( not permutation) ;
end ;
def tri_bulle( tableau) :
permutation = True
passage = 0
while permutation == True :
permutation = False
passage = passage + 1
for en_cours in range ( 0 , len ( tableau) - passage) :
if tableau[ en_cours] > tableau[ en_cours + 1 ] :
permutation = True
# On echange les deux elements
tableau[ en_cours] , tableau[ en_cours + 1 ] = \
tableau[ en_cours + 1 ] ,tableau[ en_cours]
return tableau
void tri_bulle( int * tableau)
{
int passage = 0 ;
bool permutation = true ;
int en_cours;
while ( permutation) {
permutation = false ;
passage ++;
for ( en_cours= 0 ; en_cours< 20 - passage; en_cours++ ) {
if ( tableau[ en_cours] > tableau[ en_cours+ 1 ] ) {
permutation = true ;
// on echange les deux elements
int temp = tableau[ en_cours] ;
tableau[ en_cours] = tableau[ en_cours+ 1 ] ;
tableau[ en_cours+ 1 ] = temp;
}
}
}
}
