Puisqu’une transposition peut toujours se réaliser par échanges d’éléments consécutifs, il en va de même pour une permutation quelconque. Voici une méthode de tri
fondée sur cette propriété.
Le tri à bulles
On dispose de données a 1 , a 2 , . . . , a n deux à deux comparables que l’on veut classer
par exemple par ordre croissant ; ces données peuvent être des nombres, ou encore
des chaînes de caractères qu’on classera selon leur longueur.
Notons a ≺ b la propriété « a est plus petit ou égal à b ». Cette relation doit être une
relation d’ordre, c’est-à-dire que l’on a :
a ≺ a , (a ≺ b et b ≺ c) =⇒ a ≺ c , (a ≺ b et b ≺ a) =⇒ a = b.
Initialement, les données sont présentées en désordre dans une liste ou un tableau.
Principe du tri à bulles. Il consiste à parcourir la liste en commençant par la fin
et en effectuant un échange à chaque fois que l’on trouve deux éléments successifs
qui ne sont pas dans le bon ordre.
Exemple. La liste à trier est [12, 15, 7, 5, 9, 2].
12
15
7
5
9
2
2
9
2
5
2
7
2
15
2
12
2
12
15
7
5
9
5
7
5
15
5
12
2
5
12
15
7
9
7
15
7
12
2
5
7
12
15
9
9
15
9
12
2
5
7
9
12
15
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
étape 1
étape 2
étape 3
étape 4
étape 5
étape 1 : le nombre 2 étant le plus petit, il est successivement échangé avec tous
les éléments de la liste.
étape 2 : le nombre 5 est échangé successivement avec 7, 15 et 12 qui sont supérieurs.
étape 3 : on échange 7 avec 15, puis avec 12.
étape 4 : maintenant, 15 précède 9, donc on les échange, puis on échange 9 et
l’élément 12 qui le précède.
étape 5 : il n’y a plus d’échange possible, donc la liste est triée selon l’ordre croissant.
Cet algorithme doit son nom au fait que les éléments « les plus légers remontent » vers
le haut de la liste, comme des bulles de gaz dans un liquide. S’il y a n données à trier,
le nombre d’échanges à effectuer est au maximum n−1 à la première étape, n−2 à la
deuxième, etc ; le nombre maximum d’échanges est donc 1+2+· · ·+(n−1)=n(n−1)/2.
Puisqu’un échange a ↔ b se réalise par une succession (c ← a), (a ← b), (b ← c) de
trois affectations, il faut au plus 3n(n−1)/2 opérations pour trier n données.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 77
fondée sur cette propriété.
Le tri à bulles
On dispose de données a 1 , a 2 , . . . , a n deux à deux comparables que l’on veut classer
par exemple par ordre croissant ; ces données peuvent être des nombres, ou encore
des chaînes de caractères qu’on classera selon leur longueur.
Notons a ≺ b la propriété « a est plus petit ou égal à b ». Cette relation doit être une
relation d’ordre, c’est-à-dire que l’on a :
a ≺ a , (a ≺ b et b ≺ c) =⇒ a ≺ c , (a ≺ b et b ≺ a) =⇒ a = b.
Initialement, les données sont présentées en désordre dans une liste ou un tableau.
Principe du tri à bulles. Il consiste à parcourir la liste en commençant par la fin
et en effectuant un échange à chaque fois que l’on trouve deux éléments successifs
qui ne sont pas dans le bon ordre.
Exemple. La liste à trier est [12, 15, 7, 5, 9, 2].
12
15
7
5
9
2
2
9
2
5
2
7
2
15
2
12
2
12
15
7
5
9
5
7
5
15
5
12
2
5
12
15
7
9
7
15
7
12
2
5
7
12
15
9
9
15
9
12
2
5
7
9
12
15
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
←
→
étape 1
étape 2
étape 3
étape 4
étape 5
étape 1 : le nombre 2 étant le plus petit, il est successivement échangé avec tous
les éléments de la liste.
étape 2 : le nombre 5 est échangé successivement avec 7, 15 et 12 qui sont supérieurs.
étape 3 : on échange 7 avec 15, puis avec 12.
étape 4 : maintenant, 15 précède 9, donc on les échange, puis on échange 9 et
l’élément 12 qui le précède.
étape 5 : il n’y a plus d’échange possible, donc la liste est triée selon l’ordre croissant.
Cet algorithme doit son nom au fait que les éléments « les plus légers remontent » vers
le haut de la liste, comme des bulles de gaz dans un liquide. S’il y a n données à trier,
le nombre d’échanges à effectuer est au maximum n−1 à la première étape, n−2 à la
deuxième, etc ; le nombre maximum d’échanges est donc 1+2+· · ·+(n−1)=n(n−1)/2.
Puisqu’un échange a ↔ b se réalise par une succession (c ← a), (a ← b), (b ← c) de
trois affectations, il faut au plus 3n(n−1)/2 opérations pour trier n données.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 77