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.

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 )

1. PROCEDURE tri_Insertion ( Tableau a[1:n])
2.     POUR i VARIANT DE 2 A n FAIRE
3.         INSERER a[i] à sa place dans a[1:i-1];
4. 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

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