Algorithmes de tri

Tri par insertion

Le tri par insertion, très souvent utilisé pour trier des cartes, procède comme suit:

Mise en application du tri par insertion sur une liste d'entiers

Cette méthode de tri considère les éléments de gauche à droite en insérant chacun à sa place parmi ceux déjà triés situés sur sa gauche. Pour insérer l'élément couramment considéré, on déplace simplement les éléments qui lui sont supérieurs un cran vers la droite et on l'insère dans la place laissée vacante, comme le montre la figure ci-dessous:

algo2.jpg

Déroulement du tri par sélection sur une liste d'entiers

Les éléments situés à gauche de l'indice i sont dans le bon ordre relatif pendant le tri, mais ne sont pas toujours à leur position finale puisqu'ils peuvent être déplacés pour laisser la place à des éléments inférieurs rencontrés par la suite. Malgré tout, la liste est entièrement triée lorsque l'indice atteint l'extrémité droite de la liste.

A vous de jouer !

En vous basant sur les exemples présentés ci-dessus, répondez à chacun des points suivants:

  1. Appliquez le tri par insertion sur les 9 cartes d'une même famille de cartes.
  2. Décrivez chacune des étapes de progression du tri par insertion appliqué à la liste [91, 17, 2, 35, 54]. Au besoin, recourez au programme TestInsertion vous permettant de valider votre réponse.
  3. Pour chacune des listes suivantes, calculez le nombre de comparaisons et le nombre de déplacements d'éléments nécessaires à son tri puis généralisez vos résultats pour des listes similaires comportant 10, 100 puis n éléments. Au besoin, recourez au programme AnalyseComplexite vous permettant de valider vos réponses.
    1. croissante = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    2. decroissante = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    3. aleatoire = [54, 26, 93, 31, 77, 17, 44, 55, 20, 36]
  4. Implémentez le tri par insertion en Python en vous basant sur le squelette téléchargeable ici.

|