Vers le tri par insertion

Comme dans tous les autres algorithmes de tri que nous allons étudier, nous allons travailler en place. Cela signifie que nous ne travaillons que sur la liste initiale, sans en créer de nouvelles. Le tri sera fait en permutant des éléments.

• On traite successivement toutes les valeurs à trier, en commençant par celle en deuxième position.
• Traitement : tant que la valeur à traiter est inférieure à celle située à sa gauche, on échange ces deux valeurs. On procède par permutations.

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 = ...