Aller au contenu

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 :

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

Code à trous ⭐ ⭐ ⭐ ⭐
Python
1
2
def tri_insertion(lst):
    '''trie en place la liste lst donnée en paramètre'''
Code à trous ⭐ ⭐ ⭐
Python
1
2
3
4
5
6
7
def tri_insertion(lst):
    '''trie en place la liste lst donnée en paramètre'''
    for i in range(..., ...):                 
        ... = ...                                    
        while ... > ... and ... > ... :      
            ..., ... = ..., ...      
            ... = ...
Code à trous ⭐ ⭐
Python
1
2
3
4
5
6
7
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 ⭐
Python
1
2
3
4
5
6
7
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 = ...