Tri par insertion

On souhaite dans cet exercice coder le tri par insertion en Python.

Cet algorithme de tri repose sur une fonction insere qui prend en paramètre un tableau de valeurs partiellement trié et un indice i strictement positif. On garantit que le tableau est trié jusqu'à l'indice i - 1.

La fonction insère au bon endroit parmi les indices 0 à i la valeur d'indice i suivant cet algorithme :

• on mémorise la valeur à insérer,

• tant que l'indice i est strictement positif et que la valeur à l'indice i - 1 est strictement supérieure à la valeur à insérer :

  • on la copie à la position i,

  • on décrémente i ;

• une fois la boucle terminée, on écrit la valeur à insérer à la position i.

Le tri par insertion consiste alors à parcourir le tableau à partir de l'indice 1 et à insérer la valeur courante en utilisant la fonction insere.

Objectif

On demande d'écrire les fonctions insere et tri_insertion.

Exemples

🐍 Console Python

>>> tableau = [3, 1, 2]
>>> insere(tableau, 1)
>>> tableau
[1, 3, 2]
>>> tri_insertion(tableau)
>>> tableau
[1, 2, 3]

🐍 Console Python

>>> tableau = [-10, -1, 3, 7, -2, 0, 2]
>>> insere(tableau, 4)
>>> tableau
[-10, -2, -1, 3, 7, 0, 2]
>>> tri_insertion(tableau)
>>> tableau
[-10, -2, -1, 0, 2, 3, 7]