Aller au contenu

Tri à bulles d'un tableau⚓︎

Principe du tri à bulles

On parcourt le tableau de la fin vers le début, avec la variable d'indice \(i\).

  • Pour chaque parcours avec \(i\), on parcourt le tableau avec un indice \(j\) en allant du début jusqu'à \(i\) (ou presque) ; si deux éléments consécutifs autour de l'indice \(j\) sont mal rangés, on les échange.

Objectifs : Écrire une fonction telle que tri_bulles(nombres) opère un tri en place du tableau nombres.

  • La fonction ne renvoie rien, (à part None) ; inutile de placer return.
  • Le tableau nombres est modifié par la fonction ; on parle donc de tri en place.

Compléter le code Python ci-dessous qui implémente la fonction tri_bulles.

🐍 Script Python
def tri_bulles(nombres):
    n = len(nombres)
    for i in range(..., ..., -1):
        for j in range(i):
            if nombres[j] > nombres[...]:
                # nombres[j] et nombre[j + 1] à échanger
                ...

Exemples

🐍 Console Python
>>> nb_premiers = [2, 11, 3, 7, 5]
>>> tri_bulles(nb_premiers)
>>> nb_premiers
[2, 3, 5, 7, 11]
🐍 Console Python
>>> seul = [42]
>>> tri_bulles(seul)
>>> seul
[42]
🐍 Console Python
>>> vide = []
>>> tri_bulles(vide)
>>> vide
[]
###
# testsbksl-nlbksl-nlnbpy-undpremiers = [2, 11, 3, 7, 5]bksl-nlnbpy-undpremierspy-undtrie = [2, 3, 5, 7, 11]bksl-nltripy-undbulles(nbpy-undpremiers)bksl-nlassert len(nbpy-undpremiers) == len(nbpy-undpremierspy-undtrie), "Erreur, le tableau ne doit pas changer de taille"bksl-nlfor a, b, in zip(nbpy-undpremiers, nbpy-undpremierspy-undtrie):bksl-nl assert a == b, "Erreur lors du tri de [2, 11, 3, 7, 5]"bksl-nlbksl-nlbksl-nlseul = [42]bksl-nlseulpy-undtrie = [42]bksl-nltripy-undbulles(seul)bksl-nlassert len(seul) == 1, "Erreur, le tableau [42] ne doit pas changer de taille"bksl-nlassert seul[0] == 42, "Erreur, un élément seul est déjà trié"bksl-nlbksl-nl# autres testsbksl-nlbksl-nlfrom random import samplebksl-nlfor i in range(10):bksl-nl nombres = list(sample(range(10py-strpy-str9), 100+i))bksl-nl attendu = sorted(nombres)bksl-nl tripy-undbulles(nombres)bksl-nl assert len(nombres) == len(attendu), "Erreur, le tableau ne doit pas changer de taille"bksl-nl for a, b, in zip(nombres, attendu):bksl-nl assert a == b, "Erreur lors du tri"bksl-nlbksl-nl 5/5

def tripy-undbulles(nombres):bksl-nl n = len(nombres)bksl-nl for i in range(..., ..., -1):bksl-nl for j in range(i):bksl-nl if nombres[j] > nombres[...]:bksl-nl # nombres[j] et nombre[j + 1] à échangerbksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlnbpy-undpremiers = [2, 11, 3, 7, 5]bksl-nlnbpy-undpremierspy-undtrie = [2, 3, 5, 7, 11]bksl-nltripy-undbulles(nbpy-undpremiers)bksl-nlassert len(nbpy-undpremiers) == len(nbpy-undpremierspy-undtrie), "Erreur, le tableau ne doit pas changer de taille"bksl-nlfor a, b, in zip(nbpy-undpremiers, nbpy-undpremierspy-undtrie):bksl-nl assert a == b, "Erreur lors du tri de [2, 11, 3, 7, 5]"bksl-nlbksl-nlbksl-nlseul = [42]bksl-nlseulpy-undtrie = [42]bksl-nltripy-undbulles(seul)bksl-nlassert len(seul) == 1, "Erreur, le tableau [42] ne doit pas changer de taille"bksl-nlassert seul[0] == 42, "Erreur, un élément seul est déjà trié"bksl-nlbksl-nlNone

A

Z

Retour en haut de la page