Aller au contenu

Vers le tri par insertion⚓︎

image

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 ⭐ ⭐ ⭐ ⭐
🐍 Script Python
1
2
def tri_insertion(lst):
    '''trie en place la liste lst donnée en paramètre'''
Code à trous ⭐ ⭐ ⭐
🐍 Script 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 ⭐ ⭐
🐍 Script 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 ⭐
🐍 Script 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 = ...