Tri par sélection

Le tri par sélection consiste à découper la liste en deux parties :

  • Une partie triée située en début de liste

  • Une partie non triée située en fin de liste

Initialement, la première partie est vide. Afin de la faire grossir, on va chercher dans la partie non triée la valeur la plus petite.

Une fois trouvée, elle est échangée avec la première valeur de la partie non triée, et la zone de la parte triée est étendue jusqu'à cette nouvelle valeur.

Animation représentant le tri par sélectionInformations[1]

Une animation en ligne permet également de visualiser l'algorithme. Bien sélectionner « SEL » en haut.

MéthodeProgrammation en Python

Pour réaliser le tri par sélection en Python, il faut séparer les étapes en fonctions pour simplifier le programme final :

  • Une première fonction echange(l, i, j) permet d'échanger de place deux valeurs d'indices i et j dans la liste l.

    • Exemple : Si l = [1, 6, 4, 2], alors echange(l, 1, 2) modifie l, et si on print(l) on a comme affichage [1, 4, 6, 2].

1
def echange(l, i, j):
2
    # Enregistrer dans une variable la valeur de l[i]
3
    valeur_i = l[i]
4
    # Enregistrer dans une variable la valeur de l[j]
5
    valeur_j = l[j]
6
    # Affecter dans l[i] la valeur de l[j] depuis la variable
7
    l[i] = valeur_j
8
    # Affecter dans l[j] la valeur de l[i] depuis la variable
9
    l[j] = valeur_i
10
11
12
l = [1, 2, 3, 4]
13
echange(l, 2, 1)
14
print(l)  # [1, 3, 2, 4]
  • Une deuxième fonction indice_min(l, debut) renvoie l'indice de la valeur minimale dans l à partir de l'indice debut.
    • Exemple : Si l = [1, 6, 4, 2], alors indice_min(l, 1) regarde la valeur minimale à partir de l'indice 1 (valeur 6) et trouve 2 comme valeur minimale. La fonction renvoie donc 3 (l'indice de la valeur 2).
1
def indice_min(l, debut):
2
    # Sauvegarder dans deux variables (qui serviront à
3
    # stocker la valeur minimale et son indice) les valeurs
4
    # initiales l[debut] et debut respectivement.
5
    valeur_minimale = l[debut]
6
    indice_minimal = debut
7
    
8
    # Parcourir toutes les valeurs de l[debut] à la fin de l
9
    for i in range(debut, len(l)):
10
        # Si la valeur courante est plus petite que la
11
        # valeur minimale enregistrée, mettre à jour la
12
        # valeur et son indice.
13
        if l[i] < valeur_minimale:
14
            valeur_minimale = l[i]
15
            indice_minimal = i
16
        
17
    # Renvoyer l'indice de la valeur minimale
18
    return indice_minimal
19
20
21
print(indice_min([4, 7, 3, 2], 1)) # 3
  • La fonction principale tri_selection(l) qui trie la liste l.
1
def tri_selection(l):
2
    # Tri par sélection de l (voir cours)
3
    for i in range(len(l)):
4
        indice = indice_min(l, i)
5
        echange(l, i, indice)
6
7
8
l = [4, 7, 9, 8, 2, 4, 1, 7]
9
tri_selection(l)
10
print(l)  # [1, 2, 4, 4, 7, 7, 8, 9]