Tri par insertion

Tris • Exercices 1A

flowchart TD Start([Début : Tableau T de N éléments]) --> Init[i = 1] Init --> Cond_i{i <= N ?} Cond_i -->|Faux| End([Fin : tableau trié]) Cond_i -->|Vrai| SaveKey["Traiter l'élément à insérer
clé = T[i]
j = i"] SaveKey --> Cond_j{"j > 0
ET
T[j-1] > clé ?"} Cond_j -->|Vrai| Shift["Faire monter T[j-1]
T[j] = T[j-1]
j = j - 1"] Shift --> Cond_j Cond_j -->|Faux| Insert["Insérer l'élément à la bonne place
T[j] = clé"] Insert --> Inc_i["i = i + 1"] Inc_i --> Cond_i

1

Indice

Parcourir le tableau à partir du deuxième élément (le premier élément constitue un sous-tableau déjà trié) et insérer l'élément en cours à la bonne place dans la partie inférieure (gauche) du tableau.

Écrire une fonction tri_insertion_imperatif(tab: list[int]) -> None qui trie le tableau tab en place par l'algorithme du tri par insertion itératif. Par exemple tri_insertion_imperatif([3, 1, 2]) modifie le tableau en [1, 2, 3].
2

Indice

Pour le cas de base, il est facile d'insérer un élément dans une liste vide. Puis, comparer l'élément avec le premier élément...

Écrire une fonction insert_elem(L: list[int], e: int) -> list[int] qui renvoie la liste L avec l'élément e inséré à la position correcte pour conserver l'ordre trié. Par exemple insert_elem([1, 3, 5], 4) renvoie [1, 3, 4, 5].
3

Indice

Trier récursivement par insertion, c'est insérer le premier élément dans le reste du tableau trié. Ne pas oublier qu'un tableau possédant zéro ou un seul élément est déjà trié.

Écrire une fonction insert_sort(L: list[int]) -> list[int] qui renvoie une nouvelle liste triée par l'algorithme du tri par insertion récursif. Par exemple insert_sort([3, 1, 2]) renvoie [1, 2, 3].