Tri à bulles — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 14)

Tri à bulles

Les tris · niveau 1 (application)

Énoncé

Le tri à bulles parcourt $T [0 : k]$ en échangeant deux voisines mal ordonnées, ce qui fait « remonter » le maximum en case $k - 1$ , pour $k = n, n - 1, \dots, 2$ . Donner son invariant, le programmer (en s'arrêtant dès qu'un parcours ne fait aucun échange), et donner sa complexité dans le pire et le meilleur cas. Montrer que le nombre d'échanges est égal au nombre d'inversions du tableau (exercice 13.6).

Corrigé

Invariant : « $T [k : n]$ est trié et $T [0 : k] \leq T [k : n]$ ». Un parcours de $T [0 : k]$ qui échange les voisines mal ordonnées amène le maximum de $T [0 : k]$ en case $k - 1$ : l'invariant devient vrai pour $k - 1$ .


nom : T
valeurs : 4 1 3 7 2 6 5 8
vert : 7
pointeurs : k=7
zone : 0..6 au plus 8
legende : premier parcours sur [4, 7, 1, 3, 8, 2, 6, 5] : 8 remonte en case 7


static void triBulles(int[] T) { int n = T.length;
    // I(k) : T[k:n] est trié et T[0:k] <= T[k:n]
    for (int k = n; k > 1; k--) {
        boolean echange = false;
        for (int i = 0; i + 1 < k; i++)      // le max de T[0:k] remonte en k-1
            if (T[i] > T[i + 1]) { echanger(T, i, i + 1); echange = true; }
        if (!echange) return;                 // T[0:k] est déjà trié
    }
}

Pire cas (tableau décroissant) : $n (n - 1) /2$ comparaisons et autant d'échanges, $Θ (n^{2})$ . Meilleur cas (tableau trié) : un seul parcours sans échange, $n - 1$ comparaisons, $Θ (n)$ .

Échanger deux voisines $T [i] > T [i + 1]$ supprime exactement une inversion (celle de ce couple) et ne change pas les autres : le couple formé avec toute autre case garde le même ordre relatif. Le tri se termine avec $0$ inversion : il a fait autant d'échanges que le tableau avait d'inversions.


14.10 bulles : [1, 2, 3, 4, 5, 6, 7, 8], 13 echanges, 13 inversions