Comment fonctionne le tri à bulle (anglais: « Bubble Sort »)?

Le tri à bulle est un des algorithmes parmi les plus simple permettant de trier un tableau d'objets pouvant être comparés (entiers, reels, chaîne de caractères ou n'importe quel objet pour lequel a été implémenté une fonction de comparaison).


Figure: Schéma réprésentant le principe de fonctionnement du tri à bulle (Bubble sort).

Principe
Le principe de fonctionnement du tri à bulle est décrit sur le dessin ci-dessus en considérant l'exemble d'un tableau A d'entiers désordonnés de longeur n. On prend la 1ère valeur du tableau et on la compare avec la 2ème. Si la 1ère est plus grande, les deux valeurs sont échangée (figure, étape 1). Cette opération est répétée pour les positions 2 et 3 du tableau (figure, étape 2), puis pour les positions 3 et 4 (figure, étape 3), et ainsi de suite jusqu'à ce que le plus grand élément du tableau "remonte" (comme une bulle) vers le sommet (figure, étape 5). La case bleue du tableau contient la valeur la plus élevée de la suite d'entiers initiale (figure, étape 5). On répète la même procédure pour le sous-tableau A[1..n-1] jusqu'à ce que le 2ème plus grand élément du tableau initial remonte jusqu'à l'avant dernière position du tableau. On continue comme cela jusqu'à ce que le tableau A soit complètement ordonné.

Invariants:
Au début de chaque itération de la boucle extérieur, le sous-tableau A[i+1..n] est trié et contient les n-i plus grands éléments du tableau A original.

Au début de chaque itération de la boucle intérieur, les éléments à gauche de l'élément A[j] sont tous inférieurs ou égaux à A[j]

Pseudo-code
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
Entrée: tableau A=<a1, a2, ..., an> non-ordonné de longeur n
Sortie: permutatio <a'1, a'2, ..., a'n> de la suite A donnée en entrée 
tel que a'1 <= a'2 <= ... <= a'n
TRI-BULLE(A)
pour i <- longueur[A] à 1 faire
    pour j <- 1 à longeur[A]-1 faire
        si A[j] < A[j+1] alors
            permuter A[j] et A[j-1]
Complexité:
Le temps d'exécution du tri à bulle est O(n^2) dans le pire des cas (tableau A trié initiallement dans l'ordre inverse) comme dans le cas moyen. L'opération de permutation demande toutefois pas mal de resources et un algorithme tel que le tri par insertion, dont la complexité est également de O(n^2) dans le pire des cas, aura un temps d'exécution plus rapide.

Auteur :mujigka