TP-Cours ITC 09

Tri par insertion ou tri du joueur de cartes

I. Généralités, premiers pas vers un algorithme

Comme dans le TP-Cours n°05 (tri à bulles), on s’intéressera ici au tri par ordre croissant usuel d’une liste/d’un tableau d’entiers, c’est-à-dire que la liste $L$ de longueur $n \in N^{*}$ sera considérée comme triée si pour tout $(i, j) \in [[0; n - 1]]^{2}$ , $i ⩽ j ⟹ L [i] ⩽ L [j]$
Cette propriété revient également à dire que pour tout $i \in [[0; n - 2]], L [i] ⩽ L [i + 1]$ .

Mais alors, le tri par insertion ou tri du joueur de cartes, c'est quoi au juste ?

Une première réponse dans cette "danse roumaine"

Le tri par insertion considère chaque élément du tableau et l’insère à la bonne place parmi les éléments déjà triés. Ainsi, au moment où on considère un élément, les éléments qui le précèdent sont déjà triés, tandis que les éléments qui le suivent ne sont pas encore triés.

Pour trouver la place où insérer un élément parmi les précédents, il faut le comparer à ces derniers, et les décaler afin de libérer une place où effectuer l’insertion (toujours à gauche de la position de départ de l’élément à placer). Le décalage terminé, une place laissée libre pour l’élément considéré (il faut donc le stocker dans une variable temporaire) qui est donc positionné « à sa place » parmi les éléments déjà triés.

Voici l’algorithme permettant de placer $L [3]$ parmi ses prédécesseurs dans $L$ quand ceux-ci ont déjà été ordonnés.

Pour aller plus loin et comprendre ce qui se passe lors de la première, deuxième, troisième étape de l’algorithme, etc … suivez attentivement la vidéo ci-dessous, cela ne durera pas plus de 2 minutes !

Pour ordonner les deux premiers éléments de $L$ , l’algorithme du tri par insertion compare $a P l a c e r = L [1]$ à $L [0]$ , affecte $L [0]$ à $L [1]$ si $a P l a c e r < L [0]$ et le cas échéant, affecte $a P l a c e r$ à $L [0]$ . Dès lors, les 2 prermiers éléments de $L$ sont ordonnés.

Notons $n \in N^{*}$ le nombre d’éléments de $L$ . Si $i \in [[1; n - 1]]$ , alors après $i$ étapes de l’algorithme, les $i + 1$ premiers éléments de $L$ sont rangés par ordre croissant et le reste de la liste est non trié.

Exemple : $L = [29, 22, 15, 6, 34]$

Dans cet exemple, on a appliqué un tri par insertion pour ranger par ordre croissant les éléments de la liste $L = [29, 22, 15, 6, 34]$ . Ce tri a été effectué en quatre étapes puisque cette liste $L$ contient 5 éléments entiers. À l’étape $i \in [[1; n - 1]]$ de l’algorithme, on a représenté en rose l’élément $L [i]$ que l’on compare aux éléments qui le précèdent tant s’ils sont strictement plus grands que cet élément numéro $L [i]$ . À la fin de chaque étape, ce $i + 1$ -ème élément du tableau prend sa place parmi les éléments situés à sa gauche et déjà triés.

Le nombre de comparaisons effectué sur le tableau pour l’ordonner sera appelé complexité de l’algorithme et nous permettra de déterminer un « temps de calcul » de notre algorithme sur un tableau/une liste de longueur $n \in N^{*}$ . Cette complexité sera étudiée dans la partie II et pourra être comparée à la complexité d’autres algorithmes de tris que nous étudierons cette année.

Question 1

À l’aide des explications précédentes et de l’algorithme donné dans cette partie, écrire la fonction Python

triInsertion(L:list)⟶None

triInsertion(L:list)⟶Nonequi modifie la liste d’entiers

L

pour qu’elle soit ordonnée à l’aide de l’algorithme du tri par insertion et ne renvoie aucune valeur (

return None

return None).

Vous pourrez tester votre fonction sur la liste $L = [29, 22, 15, 6, 34]$ puis lancer une batterie de tests sur votre fonction afin de valider son utilisation sur divers exemples.

II. Caractéristiques d'un tri, complexité de l'algorithme

Question 2

Lire le fichier csv Villes.csv (encodé en utf-8) contenant sur chaque ligne le nombre de milliers d’habitants suivi du nom d’une ville où habite cette population. Le séparateur de champ est le caractère

";"

";" donc chaque ligne a la forme :

habitants;nomVille

habitants;nomVille

où habitants est une chaîne de caractères contenant uniquement des chiffres et pouvant être transformée en objet de type int. La lecture du fichier doit conduire à la création d’une liste

listeVilles

listeVilles formée d’éléments de la forme

(h, v)

(h, v) où h est un entier et v une chaîne contenant un nom de ville.

Nous allons voir ici plusieurs caractéristiques que peuvent posséder (ou pas) les algorithmes de tri étudiés cette année.

Définition 1

Un algorithme de tri est dit comparatif s’il est basé sur la comparaison des éléments du tableau à trier, entre eux.

Définition 2

Un algorithme de tri est dit itératif s’il est basé sur plusieurs parcours itératifs du tableau à trier.

Définition 3

On parle de tri en place si un algorithme de tri n’utilise qu’un espace mémoire de taille constante en plus de l’espace nécessaire pour stocker le tableau à trier. En particulier, un tel algorithme n’utilise pas de tableau auxiliaire lorsqu’il est implémenté.

Définition 4

Un tri est dit stable s’il préserve l’ordonnancement initial des éléments que l’ordre considère comme égaux. De manière plus savante, on dit qu’un algorithme de tri est stable s’il ne modifie pas l’ordre initial des éléments (d’un tableau) de clés identiques .

L’intérêt d’un tri stable est qu’on peut appliquer ce tri successivement, avec des critères différents et obtenir un ordre combinant les deux critères de tri utilisés.

Imaginez, par exemple, que dans le cadre d’une certaine pandémie, vous vouliez trier une liste de personnes en fonction de la catégorie d’âge. Vous obtenez une liste avec les personnes les plus âgées en premier. Si maintenant, vous voulez effectuer un nouveau tri de cette liste en fonction du poids des individus, car les personnes en surpoids représentent une population à risque, vous aurez, si l’algorithme de tri est stable, les personnes les plus lourdes en premier et, pour les personnes de même poids, celles qui sont les plus âgées en premier.

Un algorithme non-stable ne garantirait pas alors que cela permettrait, par exemple, d’organiser une campagne de vaccination ciblée vers les populations les plus fragiles.

Question 3

En partant de la fonction

triInsertion(L:list)⟶None

triInsertion(L:list)⟶None, écrire la fonction Python

triInsertion2(L:list)⟶None

triInsertion2(L:list)⟶Nonequi modifie la liste

L

contenant des couples du type

(h,v)

(h,v) pour qu’elle soit ordonnée à l’aide de l’algorithme du tri par insertion selon des valeurs de

h entières.

Appliquer cette fonction à la liste

listeVilles

listeVilles . Vérifier que le tri par insertion est stable.