Aller au contenu

Tri par insertion

Sans filet !

Cet exercice n'est pas corrigé et l'éditeur ne comporte aucun test. À vous de les construire !

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]
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier