Tri par insertion
Objectifs
Le tri par insertion a été étudié en classe de 1ère. Dans ce document, après un rappel du cours de 1ère, nous allons implémenter une version récursive de cet algorithme et ensuite utiliser la possibilité que les fonctions en Python ont d’accepter des fonctions comme paramètres, afin de rendre plus générale et utile cette fonction de tri.
Tri du joueur de cartes
Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ». Comment un joueur de carte fait-il pour trier les cartes ?
- Au début, la main gauche du joueur est vide et ses cartes sont posées sur la table.
- Le joueur prend alors sur la table les cartes, une par une avec sa main droite, pour les placer dans sa main gauche.
- Pour savoir où placer une carte dans son jeu, le joueur la compare avec chacune des cartes déjà présentes dans sa main gauche, *en examinant les cartes de la droite vers la gauche*.
- *À tout moment, les cartes tenues par la main gauche sont triées* ; ces cartes étaient, à l'origine, les cartes situées au sommet de la pile sur la table.
Tri par insertion
Une correction du code à développer ci-dessous se trouve ici
Introduction
La méthode du tri par insertion est ilustré à ici , ou, de façon plus folklorique, ici .
- Visualiser la première vidéo (s’arrêter au bout de 4min40). Essayer de bien comprendre la méthode.
Algorithme itératif
Le tri par insertion est efficace lorsqu’on cherche à trier un tableau contenant un petit nombre d’élements ou un tableau dans lequel les éléments sont déjà pratiquement triés.
À chaque étape du processus, le tableau est divisé en deux sous-tableaux : le premier (indices plus petits que l’indice courant) est trié, le second (indices plus grands que l’indice courant n’est pas encore trié). On cherche la place de l’élément courant (non encore trié) dans le tableau trié.
Le tri par insertion est basé sur l’utilisation de deux boucles imbriquées :
- La première boucle, une boucle
Pour, parcourt la liste des valeurs, de la deuxième à la dernière ; - La seconde boucle, une boucle
TantQue, cherche à placer l’élément courant dans la première partie triée du tableau (indices inférieurs à l’indice courant).
Fonction tri_iter
Déclaration
Paramètre tab : tableau d’Entiers
Variables nb, i, j, clé : Entiers
Début
1.nb ⟵ len(tab)
2.Pour i variant de 1 à nb-1 Faire
3.clé ⟵ tab[i]
4.j ⟵ i - 1
5.TantQue j >= 0 et tab[j] > clé Faire
6.tab[j + 1] ⟵ tab[j]
7.j ⟵ j - 1
8.FinTantQue
9.tab[j + 1] ⟵ clé
10.FinPour
Fin
Remarque. L’algorithme du tri par insertion est un algorithme de tri en place. La réorganisation du tableau ne nécessite pas la création d’un nouveau tableau, ce qui économise de la place en mémoire.
-
Faire tourner « à la main » l’algorithme lorsque la fonction reçoit le tableau
tab = [5,2,4,6,1,3]. -
À quoi sert l’instruction, ligne 2 ?
-
Expliquer les conditions d’arrêt de la boucle
while, ligne 5. -
Implémenter la fonction en langage Python et la tester en l’appelant avec les arguments donnés à la question précédente.
-
Comment prouve-t-on, de façon générale, la terminaison d’un algorithme ?
-
Est-il nécessaire de prouver la terminaison de la boucle externe de cet algorithme ? De la boucle interne ?
-
Démontrer la terminaison de cet algorithme.
-
Comment prouve-t-on, de façon générale, la correction d’un algorithme ?
-
Définir un invariant de boucle et prouver que l’algorithme est correct.
-
Déterminer la complexité de l’algorithme.
Algorithme récursif
Fonction tri_rec
Déclaration
Paramètre tab : tableau d’Entiers
Paramètre i : Entier
Variable nb : Entier
Début
1.nb ⟵ len(tab)
2.Si i == nb Alors
3.Retourner tab
4.Sinon
5.insere(tab, i)
6.Retourner tri_rec(tab, i + 1)
7.FinSi
Fin
Fonction insere
Déclaration
Paramètre tab : tableau d’Entiers
Paramètre i : Entier
Variable temp : Entier
Début
1.Si i == 0 ou tab[i - 1] <= tab[i] Alors
2.Retourner tab[i]
3.Sinon
4.temp ⟵ tab[i - 1]
5.tab[i - 1] ⟵ tab[i]
6.tab[i] ⟵ temp
7.Retourner insere(tab, i - 1)
7.FinSi
Fin
-
Décrire le fonctionnement de l’algorithme récursif avec soin lorsque la fonction reçoit le tableau
tab = [5,2,4,6,1,3]. -
Implémenter en Python l’algorithme récursif.
Ajout d’une fonctionnalité au tri par insertion
Le tri par insertion, tel que nous l’avons implémenté, permet de trier des tableaux contenant tous les objets qui admettent < comme opérateur : int, float, str, … mais aussi tuple !!!
- Vérifier que la fonction
tri_recest bien capable de trier la liste[(7, 8), (3, 4), (1, 2), (5, 6)].
Quel est le critère de tri ?
Comment doit-on modifier nos fonctions de tri pour qu’elles trient par ordre décroissant ? Pour qu’elles trient le second élément de tuples passés comme arguments ?
Exemple de problème à traiter : Trier la liste suivante par année de naissance (ordre croissant)
L’idée est de confier la relation d’ordre à une fonction auxiliaire que l’on passe comme argument à la fonction de tri.
Cette fonction auxiliaire doit être un prédicat.
-
Modifier les fonction
tri-recetinserede façon à ce qu’elles admettent la fonctioninfcomme argument. La fonctioninfest responsable de la relation d’ordre lors du tri. -
Écrire une fonction
infqui permet de trier un tableau d’entiers par ordre croissant. -
Modifier la fonction
infde façon à ce que le tableau soit trié par ordre décroissant.