Tri à  bulles

Principe

  1. Comparer le contenu des cases n° 1 et 2
    S'ils ne sont pas dans le bon ordre, les inverser.
  2. Faire de même pour les cases n° 2 et 3, 3 et 4, ..., et ainsi de suite jusqu'à   (N-1 et N)
  3. Si au moins une inversion a été effectuée, recommencer au début du tableau
Le processus s'arrête lorsqu'au cours du « balayage » complet du tableau, aucune inversion n'a été effectuée (on effectue donc toujours un « tour pour rien »).

Algorithme

Inversion = Vrai
Tant que Inversion = Vrai

Exemple

Tableau à  trier : [7,5,1,9,2]

L'évolution du tableau est figurée ci-dessous.
Les cases colorées sont celles qui sont comparées ; la colonne Invers. indique si une inversion doit être effectuée
Les contenus en gras sont ceux qui ont été inversés.

1 2 3 4 5   Invers.   1 2 3 4 5   Invers.
1er tour   Il y a eu inversion : 3ème tour  
7 5 1 9 2   oui 1 5 2 7 9    
5 7 1 9 2   1 5 2 7 9 oui
5 7 1 9 2 oui 1 2 5 7 9  
5 1 7 9 2   1 2 5 7 9  
5 1 7 9 2   1 2 5 7 9  
5 1 7 9 2 oui Il y a eu inversion : 4ème tour
5 1 7 2 9   1 2 5 7 9    
Il y a eu inversion : 2ème tour   1 2 5 7 9  
5 1 7 2 9   oui 1 2 5 7 9  
1 5 7 2 9   1 2 5 7 9  
1 5 7 2 9   Il n'y a pas eu inversion : Fin du tri  
1 5 7 2 9 oui  
1 5 2 7 9  
1 5 2 7 9  

Exemple de programme en Visual Basic

Utilisation

Les résultats obtenus avec cette méthode sont peu performants, mais souvent meilleurs qu'avec le tri par insertion ou le tri par sélection. Elle est simple à  programmer.

Elle est plutôt à  utiliser avec des tableaux de petite ou moyenne taille.

Retour à  la table des matières des tris

Dernière mise à jour de cette page : 12/8/2007