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.

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
[]

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

###

Lancer # 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(bksl-nl nbpy-undpremierspy-undtriebksl-nl), "Erreur, le tableau ne doit pas changer de taille"bksl-nlfor (bksl-nl a,bksl-nl b,bksl-nl) 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-nlbksl-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(bksl-nl attendubksl-nl ), "Erreur, le tableau ne doit pas changer de taille"bksl-nl for (bksl-nl a,bksl-nl b,bksl-nl ) in zip(nombres, attendu):bksl-nl assert a == b, "Erreur lors du tri"bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

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(bksl-nl nbpy-undpremierspy-undtriebksl-nl), "Erreur, le tableau ne doit pas changer de taille"bksl-nlfor (bksl-nl a,bksl-nl b,bksl-nl) 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-nldef tripy-undbulles(nombres):bksl-nl n = len(nombres)bksl-nl for i in range(n - 1, -1, -1):bksl-nl for j in range(i):bksl-nl if nombres[j] > nombres[j + 1]:bksl-nl # nombres[j] et nombre[j + 1] à échangerbksl-nl nombres[j], nombres[j + 1] = nombres[j + 1], nombres[j]bksl-nlbksl-nl

A

Z