This page was exported from Enseignement de l'informatique et du numérique au lycée Boissy d'Anglas [ https://icn-isn-boissy.yj.fr/wp ] Export date:Sat Apr 19 10:07:35 2025 / +0000 GMT ___________________________________________________ Title: Tri par insertion --------------------------------------------------- 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. fichier-reponse-triTélécharger 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] tri_insert_2_listesTélécharger 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_cours tri_insertionTélécharger vous 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 --------------------------------------------------- Images: https://www.podcastscience.fm/wp-content/uploads/2014/09/fig3_tri_insertion.png https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2019/07/by-nc-sa.eu_.png --------------------------------------------------- --------------------------------------------------- Post date: 2019-06-19 11:00:15 Post date GMT: 2019-06-19 09:00:15 Post modified date: 2022-03-01 14:22:10 Post modified date GMT: 2022-03-01 13:22:10 ____________________________________________________________________________________________ Export of Post and Page as text file has been powered by [ Universal Post Manager ] plugin from www.gconverters.com