Vous avez certainement utilisé cet algorithme, C’est celui que les joueurs de cartes utilisent pour organiser leurs mains. Le joueur pioche la carte qui est en haut du tas et la place (l’insère) à la bonne position dans la main. Cet algorithme se nomme le « tri par insertion ».
Pour simplifier nous allons trier une liste de 9 valeurs
[ 8, 6, 3, 9, 2, 1, 4, 5, 7 ]
pour commencer l’explication , utilisons 2 listes
A faire:
Réaliser le même schéma avec [ 5, 12, 3, 7, 4 ] sur le document Libre Office réponse joint.
Combien de comparaison? pour trier [ 8, 6, 3, 9, 2, 1, 4, 5, 7 ]
La première valeur pas de comparaison, on la prend et la pose en premier, la deuxième valeur à classer je la compare à la première ordonnée et je la pose devant ou derrière. Pour la troisième valeur , deux comparaison et ainsi de suite jusqu’à la dernière huit comparaison donc nous avons fait 1+2+3+4+5+6+7+8 comparaison soit 36 comparaison.
A faire: à vous par extension pour une liste à n éléments:
Voici une implémentation sous python avec 2 tableaux ou listes comme le graphique ci dessus
def tri_insertion(tableau):
'''cette fonction prend en argument un tableau (tableau), et le trie avec la méthode de tri par insertion, elle renvoie le tableau trié (resultat)
exemple:
tri_insertion([22,8,32,1,69])
>>> [1,8,22,32,69]
tri_insertion([18,41,7,2,14])
>>> [2,7,14,18,41]'''
resultat=[]
longueur = len(tableau)
while len(resultat) < longueur:
'''tant que la taille du résultat n'est pas le même que celui du tableau initial'''
for indice in range(0,longueur):
compteur = 0
placer = True
if resultat == []:
resultat.append(tableau[0])
del tableau[0]
for valeur_resultat in resultat:
if tableau == []:
return resultat
if valeur_resultat < tableau[0]:
compteur += 1
elif placer:
placer = False
resultat.insert(compteur, tableau[0])
del tableau[0]
compteur = 0
if placer:
resultat.append(tableau[0])
del tableau[0] voici l’algorithme du tri par insertion ( ici une seule liste )
- PROCEDURE tri_Insertion ( Tableau a[1:n])
- POUR i VARIANT DE 2 A n FAIRE
- INSERER a[i] à sa place dans a[1:i-1];
- FIN PROCEDURE;
en python à essayer
def tri_insertion(tableau):
print(tab)#affiche la liste tab pour visualiser l'algo
for i in range(1,len(tableau)):
en_cours = tableau[i]
j = i
#décalage des éléments du tableau }
while j>0 and tableau[j-1]>en_cours:
tableau[j]=tableau[j-1]
j = j-1
#on insère l'élément à sa place
tableau[j]=en_coursvous pouvez trouver des explications supplémentaire ici:
site de podcastscience , site de David Roche et sur le site http://lwh.free.fr
Retour vers article algorithme de tri
