Tri a bulles

Le tri a bulles est l'algorithme de tri le plus simple a comprendre. Son nom vient du fait que les grands éléments remontent vers la fin de la liste comme des bulles qui remontent a la surface de l'eau.

Le principe : tu compares deux éléments voisins. Si le premier est plus grand que le second, tu les echanges. Tu fais ca pour toute la liste, et tu recommences jusqu'a ce que plus aucun echange ne soit nécessaire.

Apres le premier passage, le plus grand élément est forcement a la fin. Apres le deuxieme passage, les deux plus grands sont en place, etc.

C'est un algorithme O(n²) : pas tres rapide, mais facile a comprendre et a implémenter.

Écris une fonction tri_bulles(lst) qui trie une liste en place. La fonction ne retourne rien, elle modifie directement la liste.

Exemple :
lst = [5, 3, 8, 1, 2]
tri_bulles(lst)
Apres l'appel, lst vaut [1, 2, 3, 5, 8]

Tests (2/4)

Tri basique

lst = [5, 3, 8, 1, 2]
tri_bulles(lst)
assert lst == [1, 2, 3, 5, 8]

Deja trie

lst = [1, 2, 3]
tri_bulles(lst)
assert lst == [1, 2, 3]

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def tri_bulles(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

← Comparer les complexités Tri par selection →

solution.py

Bravo!

Tri a bulles

Tests (2/4)

Indices (3 disponibles)

Solution officielle