Problème — Débogage guidé par les tests

Modularité, mise au point et tests · niveau 3 (difficile)

Énoncé

Problème — Débogage guidé par les tests.

On fournit la fonction tri_insertion ci-dessous, censée trier une liste par ordre croissant. Elle contient un bogue. Écrire un jeu de tests révélant l'erreur, identifier la cause, puis corriger la fonction.

Corrigé


# Version buguee fournie :
# def tri_insertion(t):
#     for i in range(1, len(t)):
#         cle = t[i]
#         j = i - 1
#         while j >= 0 and t[j] < cle:   # ERREUR : < au lieu de >
#             t[j + 1] = t[j]
#             j -= 1
#         t[j + 1] = cle
#     return t

# Jeu de tests qui revele le bug :
# tri_insertion([3, 1, 2]) renvoyait [3, 2, 1] (decroissant)

def tri_insertion(t):
    """Trie la liste t par ordre croissant (tri par insertion).

    Modifie t en place et la renvoie.
    """
    for i in range(1, len(t)):
        cle = t[i]
        j = i - 1
        while j >= 0 and t[j] > cle:   # correction : > au lieu de <
            t[j + 1] = t[j]
            j -= 1
        t[j + 1] = cle
    return t

# Jeu de tests
assert tri_insertion([]) == []                 # cas limite
assert tri_insertion([5]) == [5]               # un element
assert tri_insertion([3, 1, 2]) == [1, 2, 3]   # cas general
assert tri_insertion([4, 4, 1]) == [1, 4, 4]   # doublons
assert tri_insertion([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]  # ordre inverse
print("Probleme 2 : tri corrige, tous les tests passent.")

Le test tri_insertion([3, 1, 2]) produisait [3, 2, 1] : en lisant le résultat, on repère que la liste est triée à l'envers, ce qui oriente vers la comparaison t[j] < cle. La corriger en t[j] > cle résout le problème, validé par l'ensemble du jeu de tests.