Un tri qui renvoie une liste ordonnée peut encore être incorrect : il peut avoir perdu un élément ou inversé deux enregistrements de même clé. Pour apprendre à déboguer un tri à bulles, cet atelier propose cinq fonctions volontairement fautives, des contre-exemples courts, des indices et un corrigé testé.
Le but est de relier chaque erreur à une propriété vérifiable : rester dans les bornes, conserver les éléments, terminer les passages nécessaires, arrêter au bon moment et préserver l’ordre des clés égales. Si vous découvrez l’algorithme, commencez par le guide du tri à bulles en Python, puis revenez aux exercices.
Télécharger le ZIP gratuit The Pingouin — code et tests. Sans inscription. Archive extraite et rejouée, 11 tests de référence réussis. Le vérificateur des exercices signale volontairement cinq échecs au départ ; le corrigé et les tests de référence sont fournis séparément.
Définir le contrat avant de chercher les erreurs
Dans cet atelier, la fonction doit renvoyer une nouvelle liste ordonnée par clé, conserver chaque élément avec son nombre d’occurrences et laisser l’entrée inchangée. Lorsque deux éléments ont la même clé, leur ordre initial doit rester le même : c’est la stabilité. Les données proposées sont des entiers et des couples dont le premier élément est une clé entière.
Nous utilisons sorted(..., key=...) comme résultat de référence. Python garantit la stabilité de ses tris ; sorted construit une nouvelle liste, alors que list.sort() modifie une liste sur place. Ces différences de contrat sont précisées dans la documentation officielle du tri en Python.
Pour chaque exercice, prévoyez d’abord le résultat à la main. Exécutez ensuite la fonction fautive, ouvrez l’indice si nécessaire, puis comparez votre correction au contrat. Les fonctions ci-dessous sont intentionnellement incorrectes.
Exercice A : une comparaison sort de la liste
Exécutez tri_borne([2, 1]). Repérez la dernière valeur prise par j et les deux indices utilisés dans la comparaison.
def tri_borne(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i):
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
return aIndice A
La boucle lit deux voisins, aux indices j et j + 1. La validité de j ne garantit pas celle de j + 1.
Corrigé A
Le dernier voisin est hors de la liste, ce qui déclenche IndexError. Remplacez range(n - i) par range(n - i - 1). Avec deux éléments, une seule comparaison suffit. Le test doit aussi couvrir la liste vide et la liste à un élément.
Exercice B : le résultat est ordonné, mais une valeur a disparu
Exécutez tri_echange([2, 1]). Contrôlez les occurrences des valeurs, pas uniquement leur ordre.
def tri_echange(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i - 1):
if key(a[j]) > key(a[j + 1]):
a[j] = a[j + 1]
a[j + 1] = a[j]
return aIndice B
Après la première affectation, la valeur initialement stockée à gauche est-elle encore disponible pour la seconde ?
Corrigé B
La fonction renvoie [1, 1]. La première affectation écrase 2 ; la seconde relit la valeur déjà remplacée. Utilisez un échange simultané, a[j], a[j + 1] = a[j + 1], a[j], ou une variable temporaire. Un contrôle avec Counter détecte la perte d’élément même lorsque les valeurs de sortie sont ordonnées.
Exercice C : le plus grand élément est placé, le reste ne l’est pas
Exécutez tri_retour([3, 2, 1]). Le premier passage termine par la valeur 3 à droite. Vérifiez les deux valeurs restantes.
def tri_retour(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i - 1):
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
return a
return aIndice C
Observez l’indentation de return. La boucle extérieure a-t-elle le temps d’effectuer un deuxième passage ?
Corrigé C
Le résultat fautif est [2, 1, 3]. La fonction se termine après le premier passage. Déplacez le retour hors de la boucle extérieure. Tester seulement une liste de deux éléments pouvait masquer cette erreur, car un passage y suffit.
Exercice D : le drapeau décrit seulement la dernière comparaison
Exécutez tri_drapeau([3, 2, 1, 4]). Suivez la valeur de echange pendant le premier passage, notamment lors de la dernière comparaison.
def tri_drapeau(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
echange = False
for j in range(n - i - 1):
echange = False
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
echange = True
if not echange:
break
return aIndice D
Pour arrêter le tri, il faut savoir si le passage entier a effectué un échange. Une paire déjà ordonnée ne doit pas effacer un échange précédent.
Corrigé D
La fonction renvoie [2, 1, 3, 4]. La dernière paire est déjà ordonnée et remet le drapeau à faux, malgré les échanges précédents. Supprimez la réinitialisation placée dans la boucle interne ; conservez seulement celle du début de chaque passage. L’arrêt anticipé devient alors valide après un passage complet sans échange.
Exercice E : les clés sont triées, leur ordre relatif est perdu
Utilisez tri_instable([(1, "A"), (1, "B")], key=lambda x: x[0]). Les lettres identifient les enregistrements ; seule la première valeur sert de clé.
def tri_instable(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i - 1):
if key(a[j]) >= key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
return aIndice E
Deux clés égales nécessitent-elles un échange pour obtenir l’ordre croissant ? Vérifiez le signe de comparaison.
Corrigé E
La fonction renvoie B avant A alors que leurs clés sont égales. Remplacez >= par >. Avec des entiers identiques, cette inversion serait invisible ; des enregistrements portant une identité distincte permettent de tester la stabilité. L’ordre des clés et la conservation des éléments ne suffisent pas à détecter ce défaut.
Comparer les cinq diagnostics exécutés
Voici les résultats obtenus par le programme fourni, avant correction des versions fautives. Pour l’exercice E, le tri porte sur la première valeur de chaque couple.
| Exercice | Entrée | Résultat fautif | Attendu |
|---|---|---|---|
| A — borne | [2, 1] | IndexError | [1, 2] |
| B — échange | [2, 1] | [1, 1] | [1, 2] |
| C — retour | [3, 2, 1] | [2, 1, 3] | [1, 2, 3] |
| D — drapeau | [3, 2, 1, 4] | [2, 1, 3, 4] | [1, 2, 3, 4] |
| E — stabilité | [[1, "A"], [1, "B"]] | [[1, "B"], [1, "A"]] | [[1, "A"], [1, "B"]] |
Les cinq cas échouent pour des raisons différentes. Le cas B passe le contrôle de l’ordre mais perd une valeur ; le cas E passe l’ordre des clés et la conservation des éléments mais échoue sur la stabilité. Une seule assertion comme « la sortie est croissante » ne couvre donc pas tout le contrat.
Utiliser le fichier d’exercices et son vérificateur
Le ZIP contient exercices_a_corriger.py, avec les cinq fonctions fautives sans annotations de solution, ainsi que verifier_corrections.py. Aucune bibliothèque externe n’est nécessaire. Depuis le dossier extrait :
python verifier_corrections.pyAu départ, les cinq fonctions doivent être signalées en échec et la commande se termine avec le code 1. C’est l’état normal de l’exercice. Modifiez le fichier d’exercices, relancez le vérificateur et visez cinq réussites, avec un code de sortie 0. Le rapport précise les entrées qui révèlent encore un problème.
Le corrigé commenté et les diagnostics de référence se trouvent dans atelier_tri.py :
python atelier_tri.py
python test_exemple.pyLa première commande remplace resultats.json dans le dossier courant. La seconde exécute 11 tests de référence. Ils vérifient les défauts initiaux, le corrigé et le vérificateur ; ils passent sur l’archive d’origine. Après modification du fichier d’exercices, certains de ces tests peuvent échouer parce qu’ils vérifient justement son état fautif initial. Pour votre progression, utilisez verifier_corrections.py.
Afficher le script Python complet et commenté
"""Cinq versions volontairement fautives du tri à bulles et un corrigé testé."""
from collections import Counter
import json
from pathlib import Path
def tri_borne(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i): # FAUTE A : dernière paire hors de la liste
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
return a
def tri_echange(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i - 1):
if key(a[j]) > key(a[j + 1]):
a[j] = a[j + 1] # FAUTE B : la valeur initiale est perdue
a[j + 1] = a[j]
return a
def tri_retour(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i - 1):
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
return a # FAUTE C : arrêt après le premier passage
return a
def tri_drapeau(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
echange = False
for j in range(n - i - 1):
echange = False # FAUTE D : efface les échanges précédents du passage
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
echange = True
if not echange:
break
return a
def tri_instable(valeurs, key=lambda x: x):
a = list(valeurs)
n = len(a)
for i in range(n - 1):
for j in range(n - i - 1):
if key(a[j]) >= key(a[j + 1]): # FAUTE E : échange aussi les clés égales
a[j], a[j + 1] = a[j + 1], a[j]
return a
def tri_bulles(valeurs, key=lambda x: x):
"""Nouvelle liste triée par clé, stable, sans modifier la liste d'entrée."""
a = list(valeurs)
for fin in range(len(a) - 1, 0, -1):
echange = False
for j in range(fin):
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
echange = True
if not echange:
break
return a
def diagnostiquer():
cas = [
("A — borne", tri_borne, [2, 1], lambda x: x),
("B — échange", tri_echange, [2, 1], lambda x: x),
("C — retour", tri_retour, [3, 2, 1], lambda x: x),
("D — drapeau", tri_drapeau, [3, 2, 1, 4], lambda x: x),
("E — stabilité", tri_instable, [(1, "A"), (1, "B")], lambda x: x[0]),
]
lignes = []
for nom, fonction, entree, key in cas:
attendu = sorted(entree, key=key)
try:
resultat = fonction(entree, key)
except IndexError:
resultat, erreur = None, "IndexError"
else:
erreur = None
lignes.append({
"exercice": nom, "entree": entree, "resultat_fautif": resultat,
"erreur": erreur, "attendu": attendu,
"ordre_des_cles": None if resultat is None else all(
key(resultat[i]) <= key(resultat[i + 1]) for i in range(len(resultat) - 1)),
"elements_conserves": None if resultat is None else Counter(resultat) == Counter(entree),
"identique_au_tri_stable": resultat == attendu,
"corrige": tri_bulles(entree, key),
})
return lignes
def main():
resultats = {"donnees": "Exemples pédagogiques fabriqués", "cas": diagnostiquer()}
texte = json.dumps(resultats, ensure_ascii=False, indent=2) + "\n"
Path("resultats.json").write_text(texte, encoding="utf-8")
print(texte)
if __name__ == "__main__":
main()Ce que vérifie le corrigé, et ce que l’atelier ne démontre pas
Le corrigé est comparé à sorted sur toutes les listes de longueur 0 à 5 construites avec les valeurs −1, 0 et 1 : 364 listes. Les tests contrôlent aussi la conservation des occurrences, l’absence de mutation de l’entrée, les générateurs et la stabilité sur des couples. Le vérificateur accepte le corrigé de référence et rejette les cinq versions initiales.
Ces tests couvrent complètement ce petit domaine d’entiers, pas toutes les entrées Python possibles. Ils ne constituent ni une preuve générale ni un benchmark de vitesse. Le tri à bulles reste un support d’apprentissage ; pour trier dans une application, les fonctions de tri intégrées répondent déjà à ce besoin.
Vous pouvez prolonger l’exercice en ajoutant un contre-exemple personnel à chaque correction. Pour travailler ensuite la validation de données, retrouvez les ressources Python gratuites et les exercices CSV avec indices et corrigés.
Exemple original exécuté le 23 octobre 2026 avec Python 3.12.14, bibliothèque standard uniquement. Versions et consignes dans le téléchargement. Miniature illustrative générée avec image_gen. Notre méthode éditoriale.
