Le tri à bulles

Le tri à bulles doit son nom au fait que les plus grandes valeurs « remontent » progressivement vers la fin du tableau, comme des bulles qui remontent à la surface. Le principe est simple : tu parcours le tableau et tu compares chaque paire d'éléments voisins ; s'ils sont dans le mauvais ordre, tu les échanges. Tu répètes ce parcours jusqu'à ce que plus aucun échange ne soit nécessaire.

À chaque passage complet, le plus grand élément restant remonte forcément jusqu'à sa position finale, à droite. C'est pour cela qu'on peut réduire la zone à parcourir d'un cran à chaque passage.

depart  : [5, 2, 4, 1, 3]
passe 0 : [2, 4, 1, 3, 5]   (5 remonte tout a droite)
passe 1 : [2, 1, 3, 4, 5]   (4 se place juste avant 5)
passe 2 : [1, 2, 3, 4, 5]   (3 se place juste avant 4)
passe 3 : [1, 2, 3, 4, 5]   (aucun echange -> tableau deja trie, on arrete)

La complexité est en O(n²) dans le pire cas (tableau trié à l'envers) car chaque passage compare presque tout le tableau, et il faut presque n passages. Mais avec un petit drapeau (« a-t-on fait un échange ? »), le tri à bulles devient O(n) dans le meilleur cas : si aucun échange n'a lieu lors d'un passage, le tableau est déjà trié et on peut s'arrêter immédiatement.

def tri_bulles(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        echange = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                echange = True
        if not echange:
            break
    return a

Piège classique : oublier de réduire la borne n - 1 - i (on ne doit pas revérifier la partie déjà triée à droite), et oublier le drapeau echange, qui rend l'algorithme bien plus lent sur des tableaux presque triés.