Tri à bulles

Avant de commencer

Le tri par sélection fait toujours le même nombre de comparaisons, qu'on lui donne un tableau aléatoire ou un tableau déjà trié. Peut-on faire mieux quand le tableau est presque trié ?

1. L'idée

À chaque passe, on parcourt le tableau et on échange les éléments adjacents dans le mauvais ordre. Les grandes valeurs "remontent" comme des bulles vers la fin.

On répète jusqu'à ce qu'aucun échange ne soit fait dans une passe → le tableau est trié.

T = [4, 2, 5, 1, 3]

Passe 1 :
[4,2,5,1,3] → 4>2 → échange → [2,4,5,1,3]
[2,4,5,1,3] → `4 < 5` → rien
[2,4,5,1,3] → 5>1 → échange → [2,4,1,5,3]
[2,4,1,5,3] → 5>3 → échange → [2,4,1,3,5]

Passe 2 :
... etc, jusqu'à une passe sans échange.

2. L'algorithme avec drapeau

DEF PROC Tri_Bulles(VAR T : Tab, n : entier)
  Répéter
    echange ← Faux
    Pour i de 1 à n-1 Faire
      Si T[i] > T[i+1] Alors
        Echanger(T[i], T[i+1])
        echange ← Vrai
      FinSi
    FinPour
  Jusqu'à echange = Faux
Fin Tri_Bulles

DEF PROC Tri_Bulles(VAR T : Tab, n : entier)
  Répéter
    echange ← Faux
    Pour i de 1 à n-1 Faire
      Si T[i] > T[i+1] Alors
        Echanger(T[i], T[i+1])
        echange ← Vrai
      FinSi
    FinPour
  Jusqu'à echange = Faux
Fin Tri_Bulles

PROCEDURE Tri_Bulles(VAR T : Tab; n : integer);
VAR
  i : integer;
  echange : boolean;
BEGIN
  REPEAT
    echange := false;
    FOR i := 1 TO n - 1 DO
      IF T[i] > T[i + 1] THEN
      BEGIN
        Echanger(T[i], T[i + 1]);
        echange := true;
      END;
  UNTIL NOT echange;
END;

3. Complexité

C'est l'avantage du tri à bulles sur le tri par sélection : il détecte qu'un tableau est trié et s'arrête.

4. Variante : éviter de retester la fin déjà triée

Après la passe k, les k plus grands éléments sont garantis à leur place finale (en fin de tableau). On peut limiter la passe suivante :

PROCEDURE Tri_Bulles_Opt(VAR T : Tab; n : integer);
VAR
  i, fin : integer;
  echange : boolean;
BEGIN
  fin := n - 1;
  REPEAT
    echange := false;
    FOR i := 1 TO fin DO
      IF T[i] > T[i + 1] THEN
      BEGIN
        Echanger(T[i], T[i + 1]);
        echange := true;
      END;
    fin := fin - 1;
  UNTIL NOT echange;
END;

5. Exercices

PROCEDURE Tri_Bulles_Decroissant(VAR T : Tab; n : integer);
VAR
  i : integer;
  echange : boolean;
BEGIN
  REPEAT
    echange := false;
    FOR i := 1 TO n - 1 DO
      IF T[i] < T[i + 1] THEN     { < pour décroissant }
      BEGIN
        Echanger(T[i], T[i + 1]);
        echange := true;
      END;
  UNTIL NOT echange;
END;

PROCEDURE Tri_Bulles_Compte(VAR T : Tab; n : integer; VAR nb_passes : integer);
VAR
  i : integer;
  echange : boolean;
BEGIN
  nb_passes := 0;
  REPEAT
    nb_passes := nb_passes + 1;
    echange := false;
    FOR i := 1 TO n - 1 DO
      IF T[i] > T[i + 1] THEN
      BEGIN
        Echanger(T[i], T[i + 1]);
        echange := true;
      END;
  UNTIL NOT echange;
END;

6. Erreurs fréquentes au bac

• Oublier de réinitialiser echange à Faux au début de chaque passe.
• Mettre Tant que echange = Vrai (Tant que) au lieu de Répéter…Jusqu'à → la première passe ne s'exécute jamais (puisque echange est Faux au début).
• Comparer T[i] avec T[i] au lieu de T[i+1].

7. Quiz