Tri par insertion

Le tri par insertion, comme 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

Le changement majeur est qu'au lieu de chercher la valeur minimale dans la partie non triée, on va récupérer la première valeur qu'on va insérer dans la première partie (en respectant l'ordre croissant).

C'est le tri des jeux de cartes.

Animation représentant le tri par insertionInformations[1]

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

MéthodeProgrammation

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

  • Une fonction insertion, qui insert au bon endroit la valeur passée en argument et décale le reste de la liste

  • Une fonction tri_insertion, trie la liste

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

  • La fonction insertion, prend en paramètres, la liste, et un indices et insert l’élément correspondant à l'indice au bon endroit, en supposant qu'avant l'indice la sous-liste soit triée.

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

1
insertion(l, i):
2
    valeur prend la valeur de l[i]
3
4
    j prend la valeur 0
5
6
    Tant que j est inférieur à i et que l[j] est inférieur à valeur:
7
        j est incrémenté de 1
8
9
    Tant que j est inférieur ou égal à i:
10
        valeur et l[j] sont échangés
11
        j est incrémenté de 1
  • La fonction tri_insertion prend en paramètres la liste et la trie en place, en utilisant la méthode du tri par insertion.
    Exemple : Si l = [1, 6, 4, 2], alors tri_insertion(l) modifie l, et l vaut [1, 2, 4, 6].
1
tri_insertion(l):
2
    Pour i allant de 1 à la longueur de l:
3
        on appelle insertion avec l et i