Tri à bulles

Voisins, invariant de fin, stable

← Retour au cours Tri

Algorithme complet

voisins

Compare les éléments adjacents ; le max bullle en fin.

for passe in range(nb)
Passes
range(0, nb-1-passe)
Fin déjà triée
tableau[j] > tableau[j+1]
Échange si mal ordonné
tri_bulle.py 
def tri_bulle(tableau):
    nb_elements = len(tableau)
    for passe in range(nb_elements):
        for indice in range(0, nb_elements - 1 - passe):
            if tableau[indice] > tableau[indice + 1]:
                tableau[indice], tableau[indice + 1] = (
                    tableau[indice + 1], tableau[indice]
                )

Synthèse des trois tris

comparer

Tous O(n²) en version cours ; insertion souvent le plus rapide en pratique.

Sélection
O(n²), instable
Insertion
O(n²) pire, O(n) meilleur, stable
Bulles
O(n²), stable

💻 Exemples de code

Bulles optimisé (drapeau d'arrêt)

tri_bulle_opt.py 
def tri_bulle_optimise(tableau):
    nb_elements = len(tableau)
    for passe in range(nb_elements):
        echange_effectue = False
        for indice in range(0, nb_elements - 1 - passe):
            if tableau[indice] > tableau[indice + 1]:
                tableau[indice], tableau[indice + 1] = (
                    tableau[indice + 1], tableau[indice]
                )
                echange_effectue = True
        if not echange_effectue:
            break

📋 Aide-mémoire

Bulles optimisé avec drapeau d'arrêt : O(n) si déjà trié.

Stabilité : préserve l'ordre des éléments égaux.