Aller au contenu

Tri à bulles⚓︎

Hors du programme de NSI

Le tri à bulle est intéressant à étudier mais il ne fait pas partie du programme de NSI

Le tri à bulles en bref

On parcourt les paires d'éléments et on les échange si la valeur de gauche est strictement supérieure à celle de droite.

Première approche⚓︎

Le principe du tri à bulles s'apparente à celui du tri par insertion : il s'agit de décaler des valeurs jusqu'à ce qu'elles atteignent une position convenable.

L'idée est ici de faire « remonter » les grandes valeurs vers la fin du tableau. Comme les grosses bulles dans de l'eau pétillante (source).

Bulles

L'algorithme est organisé autour de deux boucles :

  • une boucle principale parcourant tous les indices i du dernier len(tableau) - 1 (inclus) au deuxième 1 (inclus),

  • une boucle secondaire qui, à chaque itération de la boucle principale, parcourt tous les indices j entre le premier 0 (inclus) et i (inclus). Lors de cette boucle, on compare deux éléments consécutifs d'indices j et j + 1 et on les échange si celui d'indice j est strictement supérieur à celui d'indice j + 1.

Ainsi, lors de la première itération de la boucle principale, la boucle secondaire parcourt tous les éléments d'indice entre 0 et len(tableau) - 1 (inclus).

  • Lors de la première itération de cette boucle secondaire, on compare donc les valeurs d'indices 0 et 1 : si la première est strictement supérieure à la deuxième, on les échange.

  • Qu'il y ait eu échange ou non, on recommence ensuite en comparant les valeurs d'indices 1 et 2. Là encore, si elles sont mal triées, on les échange.

  • On recommence de proche en proche jusqu'à avoir comparé les deux dernières valeurs.

  • À l'issue de cette première itération de la boucle principale, la valeur maximale du tableau est remontée (comme une bulle) en fin de tableau.

  • Lors de la deuxième itération de la boucle principale, la boucle secondaire parcourt tous les éléments d'indice entre 0 et len(tableau) - 2 (inclus). On effectue les échanges comme décrit plu haut.

  • Lors du dernier tour de boucle principale, on n'effectue la comparaison que des deux premières valeurs (indices 0 et 1).

Nous verrons plus bas qu'il est possible d'optimiser cet algorithme pour qu'il s'arrête dès que le tableau est trié. L'illustration ci-dessous met en oeuvre la version optimisée.

Tableau aléatoire Tableau croissant Tableau décroissant

Trier votre tableau

La fonction tri_bulles

Compléter la fonction tri_bulles prenant en argument un tableau et le triant en place à l'aide du tri à bulle.

On pourra utiliser la fonction echange.

###
def echange(tableau, i, j):bksl-nl tableau[i], tableau[j] = tableau[j], tableau[i]bksl-nlbksl-nlbksl-nldef tripy-undbulles(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nltableaupy-und0 = [3, 1, 2]bksl-nltripy-undbulles(tableaupy-und0)bksl-nlassert tableaupy-und0 == [1, 2, 3], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableaupy-und1 = [1, 2, 3, 4]bksl-nltripy-undbulles(tableaupy-und1)bksl-nlassert tableaupy-und1 == [1, 2, 3, 4], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableaupy-und2 = [-2, -5]bksl-nltripy-undbulles(tableaupy-und2)bksl-nlassert tableaupy-und2 == [-5, -2], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableaupy-und3 = []bksl-nltripy-undbulles(tableaupy-und3)bksl-nlassert tableaupy-und3 == [], "Erreur avec un tableau vide"bksl-nlbksl-nlprint("Bravo !")bksl-nlbksl-nl

Astuce (1)

On doit utiliser deux boucles for imbriquées.

Astuce (2)

La boucle principale itère de len(tableau) - 1 inclus à 0 exclu.

Astuce (3)

Si i est la variable utilisée dans la boucle principale, la boucle secondaire itère de 0 inclus à i exclu.

Solution
🐍 Script Python
def tri_bulles(tableau):
    for i in range(len(tableau) - 1, 0, -1):
        for j in range(0, i):
            if tableau[j] > tableau[j + 1]:
                echange(tableau, j, j + 1)

Optimisation⚓︎

L'algorithme trie bien les tableaux. Une question toutefois : que se passe-t'il lorsque le tableau est trié (à un moment quelconque du déroulement) ?

Tri à bulle VS tableau trié

On fournit un tableau trié dans l'ordre croissant à l'algorithme de tri à bulles.

  • L'algorithme le trie dans l'ordre décroissant !
  • L'algorithme le trie dans un ordre aléatoire !
  • L'algorithme s'arrête à la fin de la première itération de la boucle principale
  • L'algorithme effectue toutes les itérations des deux boucles, toutes les lectures, les comparaisons, mais n'échange aucune valeur
  • ❌ Non, l'algorithme gère bien ce cas de figure
  • ❌ Non, l'algorithme gère bien ce cas de figure
  • ❌ L'algorithme s'arrête à la fin de la première itération de la boucle principale
  • ✅ L'algorithme effectue toutes les itérations des deux boucles, toutes les lectures, les comparaisons, mais n'échange aucune valeur

Et oui, dans ce cas, l'algorithme effectue toutes les itérations, toutes les comparaisons mais n'échange aucune valeur. Beaucoup de travail pour pas grand-chose...

Remarque

On peut montrer que le tri à bulles est de coût quadratique, comme les tris par sélection ou insertion.

Repérer un tableau trié

On exécute le tri à bulles. Comment savoir si le tableau est trié durant l'exécution de l'algorithme ?

  • Un tableau est trié si la valeur minimale est en première position
  • Un tableau est trié si la valeur maximale est en dernière position
  • Un tableau est trié si lors d'une itération de la boucle principale on n'a fait aucun échange
  • Un tableau est trié si lors d'une itération de la boucle principale on a fait un seul échange
  • ❌ Cela peut se produire dès le début sans que le tableau soit trié. Par exemple avec $[1,\,3,\,2]
  • ❌ Ce sera toujours le cas après une itération que le tableau soit trié ou non
  • ✅ En effet, c'est le bon critère !
  • ❌ Cela signifie simplement que la valeur maximale était en avant-dernière position

Nous avons donc notre critère. Nous pouvons optimiser l'algorithme.

La fonction tri_bulles_opt

Compléter la fonction tri_bulles_opt prenant en argument un tableau et le triant en place à l'aide du tri à bulle.

Le tri s'arrêtera dès qu'une itération se termine sans avoir effectué d'échange.

On pourra utiliser la fonction echange.

###
def echange(tableau, i, j):bksl-nl tableau[i], tableau[j] = tableau[j], tableau[i]bksl-nlbksl-nlbksl-nldef tripy-undbullespy-undopt(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nltableaupy-und0 = [3, 1, 2]bksl-nltripy-undbullespy-undopt(tableaupy-und0)bksl-nlassert tableaupy-und0 == [1, 2, 3], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableaupy-und1 = [1, 2, 3, 4]bksl-nltripy-undbullespy-undopt(tableaupy-und1)bksl-nlassert tableaupy-und1 == [1, 2, 3, 4], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableaupy-und2 = [-2, -5]bksl-nltripy-undbullespy-undopt(tableaupy-und2)bksl-nlassert tableaupy-und2 == [-5, -2], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableaupy-und3 = []bksl-nltripy-undbullespy-undopt(tableaupy-und3)bksl-nlassert tableaupy-und3 == [], "Erreur avec un tableau vide"bksl-nlbksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution
🐍 Script Python
def tri_bulles_opt(tableau):
    for i in range(len(tableau) - 1, 0, -1):
        tableau_trie = True
        for j in range(0, i):
            if tableau[j] > tableau[j + 1]:
                echange(tableau, j, j + 1)
                tableau_trie = False
        if tableau_trie:
            return

Désormais, face à un tableau initialement trié dans l'ordre croissant, l'algorithme n'effectuera qu'une seule itération. Le coût sera alors linéaire.