Tri par Insertion

On cherche à implémenter le tri par insertion, comme vu dans la partie précédente

Question

Écrire la fonction insertion, telle que :

  • Entrées :

    • Une liste l, de type list, de valeurs comparables avec '<'

    • Un entier i, compris entre 0 et len(l) et tel que l[:i] est triée

  • Sortie : Aucune

  • Effet : Insert la valeur contenue à l'indice i dans l[:i], en respectant l'ordre, et décale les valeurs au besoins.

Solution

1
def insertion(l, i):
2
    valeur = l[i]
3
4
    j = 0
5
6
    while j < i and l[j] < valeur:
7
        j += 1
8
 
9
    while j <= i:
10
        valeur, l[j] = l[j], valeur
11
        j += 1
Question
En utilisant des assert, écrire des tests pertinents et suffisant pour vérifier le bon fonctionnement de insertion.
Solution
1
l = [1, 6, 2, 4]
2
insertion(l, 0)
3
assert l == [1, 6, 4, 2]
4
5
insertion(l, 1)
6
assert l == [1, 6, 4, 2]
7
8
insertion(l, 2)
9
assert l == [1, 4, 6, 2]
10
11
insertion(l, 3)
12
assert l == [1, 2, 4, 6]
Question
Écrire la fonction tri_insertion, telle que :
  • Entrée :
    • Une liste l, de type list, de valeurs comparables avec '<'
  • Sortie : Aucune
  • Effet : Trie la liste, en utilisant la méthode du tri par insertion.
Solution
1
def tri_insertion(l: list):
2
    for i in range(1, len(l)):
3
        insertion(l, i)
Question
En utilisant des assert, écrire des tests pertinents et suffisant pour vérifier le bon fonctionnement de tri_insertion.
Solution
1
l = []
2
tri_insertion(l)
3
assert l == []
4
5
l = [1]
6
tri_insertion(l)
7
assert l == [1]
8
9
l = [1, 2]
10
tri_insertion(l)
11
assert l == [1, 2]
12
13
l = [2, 1]
14
tri_insertion(l)
15
assert l == [1, 2]
16
17
l = [1, 2, 4, 6]
18
tri_insertion(l)
19
assert l == [1, 2, 4, 6]
20
21
l = [1, 6, 2, 4]
22
tri_insertion(l)
23
assert l == [1, 2, 4, 6]