Tri par insertion
Un cas concret
Commençons par trier à la main un jeu de carte !
Cinq cartes vous ont été distribuées et vous les retournez une à une pour les ranger par ordre croissant dans votre main.
La première carte retournée est :
La deuxième carte retournée est :
Vous mettez cette carte à droite en tant que plus grosse ; votre main triée est alors :
La troisième carte retournée est :
Vous insérez cette carte entre le 5 et le 10 ; votre main triée est alors :
La quatrième carte retournée est :
Vous insérez cette carte entre le 8 et le 10 ; votre main triée est alors :
La dernière carte retournée est :
Vous insérez cette carte au debut ; votre main triée est alors :
Ainsi la liste des valeurs des cinq cartes obtenues [5, 10, 8, 9, 2] a été triée par des insertions successives en [2, 5, 8 , 9, 10]
Voici une visualisation de l'algorithme de tri par insertion avec une danse roumaine :
Le tri par insertion correspond au tri de cartes généralisé avec une liste de valeurs.
On considère les éléments de la liste un par un (comme pour les cartes) :
- le premier élément de la liste forme une liste triée à un seul élément,
- le deuxième élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais une liste triée à deux éléments,
- le troisième élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais une liste triée à trois éléments,
- ...
- le dernier élément de la liste initiale est rangée à sa place dans la liste triée : on a désormais complètement trié la liste initiale.
Voici le pseudo-code en langage naturel de ce tri :
tri_insertion(liste L indexée de 0 à n-1) Pour i allant de 1 à n-1 faire placer l'élément L[i] dans la liste déjà classée L[0:i-1] retourner la liste L
Pour placer au bon endroit l'élément L[i], il suffit de permuter cet élément avec le précédent dans la liste triée tant que cet élément précédent est plus grand (et qu'il existe !).
Voici donc le tri par insertion écrit en langage Python :
def tri_insertion(lst:list)->list:
for i in range(1,len(lst)):
elt=lst[i]
j=i
while elt < lst[j-1] and j > 0:
lst[j]=lst[j-1]
j-=1
lst[j]=elt
return lst
Tester temporairement votre code et analyser le script par étape, vous pouvez également vous rendre sur pythontutor.
Voici une liste de nombres à trier : [4,9,6,7,12,3].
Écrire l'évolution de la liste et des indices i et j étape par étape. Vous pouvez utiliser un tableau
Tri par sélection
Un cas concret
Recommençons par trier un jeu de carte à la main !
Cinq cartes vous ont été distribuées et vous les avez toutes dans un ordre quelconque dans votre main.
Supposons que les cartes en main soient :
Pour trier les cartes, l'idée est de :
- balayer l'ensemble des cartes non encore triées afin d'y repérer la plus petite.
- cette plus petite carte restante est alors placée en première position des cartes pas encore triées.
Mise en œuvre de la démarche sur l'ensemble des cinq cartes :
Aucune carte n'a déjà été triée. Parmi les 5 de l'ensemble, la plus petite est le 2 (de carreau) :
Cette carte de valeur minimale est placée en première position par une permutation de deux cartes, d'où la nouvelle configuration :
Le 2 est déjà bien placé. Parmi les 4 cartes restantes, la plus petite est le 5 (de cœur) : par hasard, il est déjà bien placé :
Deux cartes sont déjà bien placées. Parmi les 3 cartes restantes, la plus petite est le 8 (de carreau) :
Cette carte restante de valeur minimale est placée en première position des cartes restantes par une permutation de deux cartes, d'où la nouvelle configuration :
Trois cartes sont déjà bien palcés. Parmi les 2 cartes restantes, la plus petite est le 9 (de pique) :
Cette carte restante de valeur minimale est placée en première position des cartes restantes par une permutation de deux cartes, d'où la nouvelle configuration :
La dernière carte restante non triée est forcément la plus grande de toutes : aucun nouveau changement n'est nécessaire pour obtenir finalement la liste entièrement triée :
Généralités
On considère les éléments de la liste un par un (comme pour les cartes) :
- le plus petit élément de la liste est mis en première position par permutation ; on a désormais un début de liste triée à un élément,
- le deuxième plus petit élément de la liste est rangé en seconde position par permutation ; on a désormais un début de liste triée à deux éléments,
- ...
- l'avant dernier plus petit élément de la liste est rangé en avant-dernière position par permutation : on a désormais complètement trié la liste initiale.
Voici le pseudo-code en langage naturel de ce tri :
tri_selection(liste L indexée de 0 à n-1) Pour i allant de 0 à n-2 faire trouver le plus petit élement L[j] de la liste entre i et n-1 échanger les éléments L[i] et L[j] retourner la liste L
Deux fonctions seront utiles pour écrire en python cet algorithme :
- la fonction
positionnerqui renvoie l'index du minimum d'une liste entre un index nommédepartet son dernier terme. Cette liste et l'indexdepartsont entrés comme paramètres. - la fonction
permuterqui permute deux éléments d'une liste extraite entrée comme paramètre, les deux index de ces éléments étant aussi entés comme paramètres.
positionner reçoit deux paramètres en entrée :
- lst qui est la liste étudiée,
- depart qui un nombre entier qui correspond à un index.
positionner renvoie l'index du minimum de la liste extraite entrée dont les termes sont compris entre l'index depart et le dernier.
Voici le code de la fonction positionner où deux lignes sont incomplètes :
def positionner(lst: list,depart :int) -> int:
pos = depart # pos stocke la position du minimum : lst[pos] sera donc le minimum trouvé
i= pos + 1
while i<len(lst):
.......................... # ligne 5
.......................... # ligne 6
i += 1
return pos Compléter le code des lignes 5 et 6 de la fonction positionner
Voici le code de la procédure permuter où les trois lignes permettant la permutation des valeurs sont incomplètes.
Cette procédure permuter reçoit en paramètres :
- une liste lst,
- deux entiers i1 et i2 représentants deux index de cases dans cette liste.
def permuter(lst: list, i1: int, i2: int) -> None:
a = ...................... # ligne 2
.......................... # ligne 3
.......................... # ligne 4
return None Proposer ci dessous un code pour les lignes 2 à 4 permettant de compléter la procédure permuter précédente :
En utilisant la fonction positionner et la procédure permuter, proposer une procédure tri_selection qui correspond à l'algorithme de tri par sélection, c'est à dire qui prend comme paramètre une liste et qui
trie cette liste triée par ordre croissante par la méthode de tri par sélection et qui ne renvoie rien.
Pensez à vérifier la procédure écrite, par exemple avec la liste suivante : [1,8,6,4,3,9,20,7].
Pour visualiser comment cet algorithme trie une liste quelconque, accéder à un site Web en cliquant sur l'image ci-dessous :
Un fois accédé.e à ce site, cliquer sur Trier pour lancer l'application.
Voici ci-contre une animation qui permet de visualiser le tri par sélection :
- les nombres sur fond jaune sont déjà triés,
- le nombre sur fond rouge est le minimum de ceux déjà étudiés parmi les nombres encore à trier,
- le nombre sur fond bleu est celui en cours d'étude (celui dont la valeur sera comparée au minimum actuel sur fond rouge),
- la double flèche noire signifie qu'il y a permutation des valeurs ciblées.
Savoir faire et Savoir
- Écrire un algorithme de tri par insertion.
- Écrire un algorithme de recherche d'un minimum dans une liste
- Écrire un algorithme de tri par sélection.
- permutation de deux termes d'une liste