Tri à bulles - Définition

Introduction

Exemple du tri à bulles utilisant une liste de nombres aléatoires

Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme les bulles d'air remontent à la surface d'un liquide.

Le tri à bulles est souvent enseigné en tant qu'exemple algorithmique. Cependant, sa complexité est de l'ordre de n² dans le pire des cas (où n est la taille du tableau), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas utilisé en pratique.

Algorithme de base

L'algorithme parcourt le tableau, et compare les couples d'éléments successifs. Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés. Après chaque parcours complet du tableau, l'algorithme recommence l'opération. Lorsqu'aucun échange n'a lieu pendant un parcours, cela signifie que le tableau est trié. On arrête alors l'algorithme.

Pseudo-code

Voici la description en pseudo-code du tri à bulle, pour trier un tableau T de n éléments numérotés de 0 à n-1 :

       procédure tri_bulle(tableau T, entier n)           répéter               aucun_échange = vrai               pour j de 0 à n - 2                   si T[j] > T[j + 1], alors                       échanger T[j] et T[j + 1]                       aucun_échange = faux           tant que aucun_échange = faux      

Complexité

Pour un tableau de taille n, le nombre d'itérations de la boucle externe « répéter … tant que aucun_échange = faux » est compris entre 1 et n. En effet, on peut démontrer qu'après la i-ème étape, les i derniers éléments du tableau sont à leur place. À chaque itération, il y a exactement n-1 comparaisons et au plus n-1 échanges.

• Le pire cas (n itérations) est atteint lorsque le plus petit élément est à la fin du tableau. La complexité est alors Θ(n²).
• En moyenne, la complexité est aussi Θ(n²). En effet, le nombre d'échanges de paires d'éléments successifs est égal au nombre d'inversions, c'est-à-dire de couples (i,j) tels que i < j et T(i) > T(j). Ce nombre est indépendant de la manière d'organiser les échanges. Lorsque l'ordre initial des éléments du tableau est aléatoire, il est en moyenne égal à n(n-1)/4.
• Le meilleur cas (une seule itération) est atteint quand le tableau est déjà trié. Dans ce cas, la complexité est linéaire.

Exemple étape par étape

Prenons la liste de chiffres « 5 1 4 2 8 » et trions-la de manière croissante en utilisant l'algorithme de tri à bulles. Pour chaque étape, les éléments comparés sont écrits en gras.

Première étape:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ) Les éléments 5 et 1 sont comparés, et comme 5 > 1, l'algorithme les intervertit.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ) Interversion car 5 > 4.
( 1 4 5 2 8 ) ( 1 4 2 5 8 ) Interversion car 5 > 2.
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Comme 5 < 8, les éléments ne sont pas échangés.
Deuxième étape:
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Même principe qu'à l'étape 1.
( 1 4 2 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
À ce stade, la liste est triée, mais pour le détecter, l'algorithme doit effectuer un dernier parcours.
Troisième étape:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Comme la liste est triée, aucune interversion n'a lieu à cette étape, ce qui provoque l'arrêt de l'algorithme.