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

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

  • Une première fonction echange qui permet d’échanger les éléments de la liste ;

  • Une deuxième fonction indice_min qui renvoie l'indice de la valeur minimale de la liste à partir d'un certain indice ;

  • La fonction principale, tri_selection, qui trie la liste.

Voici plus en détail les fonctions spécifiées.

  • La fonction echange, prend en paramètres, la liste, et 2 indices et inverse les valeurs à ces indices.

    Exemple : Si l = [1, 6, 4, 2], alors echange(l, 1, 2) modifie l, et l vaut [1, 4, 6, 2].

1
echange(l, i, j):
2
    Enregistrer l[i] dans une variable valeur_i
3
    Enregistrer l[j] dans une variable valeur_j
4
5
    Mettre valeur_i dans l[j]
6
    Mettre valeur_i dans l[j]
  • La fonction indice_min, prend en paramètres, la liste et un indice et renvoie l'indice du minimum après l'indice (inclus) passé en paramètre.
    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
indice_min(l, i):
2
    i_min prend la valeur de i
3
4
    Pour j allant de i + 1 à la longueur de l:
5
        Si l[j] > l[i_min] alors:
6
            i_min prend la valeur de j
7
8
    renvoyer i_min
  • La fonction tri_selection prend en paramètres la liste et la trie en place, en utilisant la méthode du tri par sélection.
    Exemple : Si l = [1, 6, 4, 2], alors tri_selection(l) modifie l, et l vaut [1, 2, 4, 6].
1
tri_selection(l):
2
    Pour i allant de 0 à la longueur de l:
3
        indice prend la valeur de indice_min(l, i)
4
        on appelle echange avec l, indice et i