Vers le tri par insertion

Principe de l'algorithme

Pour toutes les valeurs, en commençant par la deuxième :

• Tant qu'on trouve à gauche une valeur supérieure et qu'on n'est pas revenu à la première valeur, on échange ces deux valeurs.

Pour tester son code :

>>> maliste = [7, 5, 2, 8, 1, 4]
>>> tri_insertion(maliste)
>>> maliste
[1, 2, 4, 5, 7, 8]

Code à trous

def tri_insertion(lst):
    '''trie en place la liste lst donnée en paramètre'''

Code à trous

def tri_insertion(lst):
    '''trie en place la liste lst donnée en paramètre'''
    for i in range(..., ...):                 
        ... = ...                                    
        while ... > ... and ... > ... :      
            ..., ... = ..., ...      
            ... = ...                              

Code à trous

def tri_insertion(lst):
    '''trie en place la liste lst donnée en paramètre'''
    for i in range(..., len(lst)):                 
        k = ...                                    
        while k > ... and lst[...] > lst[...] :      
            lst[...], lst[...] = lst[...], lst[...]      
            k = ...                               

Code à trous

def tri_insertion(lst):
    '''trie en place la liste lst donnée en paramètre'''
    for i in range(1, len(lst)):                 
        k = ...                                    
        while k > ... and lst[k-1] > lst[k] :      
            lst[k], lst[k-1] = lst[...], lst[...]      
            k = ...