Tri par sélection

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

Question

Écrire la fonction echange, telle que :

  • Entrées :

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

    • Un entier i, compris entre 0 et len(l)

    • Un entier j, compris entre 0 et len(l)

  • Sortie : Aucune

  • Effet : Échange les valeurs de l aux indices i et j

Solution

1
def echange(l: list, i: int, j: int):
2
    valeur_i = l[i]
3
    valeur_j = l[j]
4
5
    l[i] = valeur_j
6
    l[j] = valeur_i
Question
En utilisant des assert, écrire des tests pertinents et suffisants pour vérifier le bon fonctionnement de echange.
Solution
1
l = [1, 6, 4, 2]
2
3
echange(l, 0, 1)
4
assert l == [6, 1, 4, 2]
5
6
echange(l, 0, 0)
7
assert l == [6, 1, 4, 2]
8
9
echange(l, 1, 3)
10
assert l == [6, 2, 4, 1]
Question
Écrire la fonction indice_min, telle que :
  • Entrées :
    • Une liste l, de type list, de valeurs comparables avec '<'
    • Un entier i, compris entre 0 et len(l)
  • Sortie : L'indice du minimum de l[i:], la fin de l commençant en i
  • Effet : Aucun
Solution
1
def indice_min(l: list, i: int) -> int:
2
    i_min = i
3
4
    for j in range(i+1, len(l)):
5
        if l[j] < l[i_min]:
6
            i_min = j
7
8
    return i_min
Question
En utilisant des assert, écrire des tests pertinents et suffisants pour vérifier le bon fonctionnement de indice_min.
Solution
1
l = [1, 6, 2, 4]
2
3
assert indice_min(l, 0) == 0
4
5
assert indice_min(l, 1) == 2
6
7
assert indice_min(l, 2) == 2
8
9
assert indice_min(l, 3) == 3
Question
Écrire la fonction tri_selection, 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 sélection.
Solution
1
def tri_selection(l: list):
2
    for i in range(len(l)):
3
        indice = indice_min(l, i)
4
        echange(l, i, indice)
Question
En utilisant des assert, écrire des tests pertinents et suffisants pour vérifier le bon fonctionnement de tri_selection.
Solution
1
l = []
2
tri_selection(l)
3
assert l == []
4
5
l = [1]
6
tri_selection(l)
7
assert l == [1]
8
9
l = [1, 2]
10
tri_selection(l)
11
assert l == [1, 2]
12
13
l = [2, 1]
14
tri_selection(l)
15
assert l == [1, 2]
16
17
l = [1, 2, 4, 6]
18
tri_selection(l)
19
assert l == [1, 2, 4, 6]
20
21
l = [1, 6, 2, 4]
22
tri_selection(l)
23
assert l == [1, 2, 4, 6]