C18 : Exercices

C18.E1 : Tri à bulles (du plus grand au plus petit)

L’algorithme parcourt la liste et compare les éléments consécutifs. Lorsque deux éléments consécutifs ne sont pas dans l’ordre, ils sont échangés.

Après un premier parcours complet de la liste, le plus petit élément est forcément en fin de la liste, à sa position définitive.

On parcourt la liste à nouveau, en s’arrêtant à l’avant-dernier élément.

Après ce deuxième parcours, les deux plus petits éléments sont à leur positions définitives.

Il faut donc répéter les parcours de la liste, jusqu’à ce que tous les éléments soient à leurs positions définitives.

Travail à faire

Proposer un programme qui trie une liste suivant la méthode du tri à bulles.

from random import randint

def tri_bulle(liste):
    """
    Trie la liste dans l'ordre décroissant
    """
    a_trouve_echange = True
    i_max = len(liste)-1
    while a_trouve_echange and i_max > 1 :
        a_trouve_echange = False
        for j in range(0, i_max):
            if liste[j] < liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]
                a_trouve_echange = True
        i_max = i_max - 1

# ==== Programme principal ====
L = [randint(0,50) for _ in range(20)]
print(L)
tri_bulle(L)
print(L)