Tri par insertion

12.4. Tri par insertion#

12.4.1. Quelques outils pour commencer#

On commence par se donner une liste de nombres qu’on va mélanger

t = [i for i in range(10)]

t

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

from random import shuffle

shuffle(t)

t

[8, 9, 0, 4, 3, 7, 1, 5, 6, 2]

On se donne une fonction qui va échanger la valeur présente à l’indice \(i\) avec celle à l’indice \(j\).

def echanger(t: list, i: int, j: int) -> list:
    assert 0 <= i < len(t), 'Indice i en dehors des bornes'
    assert 0 <= j < len(t), 'Indice j en dehors des bornes'
    t[i],t[j] = t[j],t[i]
    return t

On peut désormais vérifier sur quelques exemples.

echanger([1,2,3],1,2)

[1, 3, 2]

echanger([0,1],1,1)

[0, 1]

12.4.2. Le tri à proprement parler#

Une écriture possible de l’algorithme est la suivante :

def tri_insertion(t: list) -> list:
    for i in range(len(t)):
        j = i
        while j > 0 and t[j-1] > t[j]:
            t = echanger(t,j-1,j)
            j = j - 1
    return t

t = [i for i in range(10)]
shuffle(t)
t

[3, 1, 7, 8, 5, 9, 6, 4, 2, 0]

tri_insertion(t)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Contenu