Algorithmes de tri

Tri de données dans une liste

Parmi les algorithmes "classiques" les plus utilisés en informatique figurent sans doute les algorithmes de tri de données

Trier des données, c'est les ranger dans un ordre particulier ( par ordre croissant, décroissant, alphabétique,...) et ceci trouve donc une application dans de nombreux domaines : tri de listes de noms, tri de la priorité des données à transmettre sur un réseau, etc...

Il en existe de très nombreux et plus ou moins complexes, comme le tri-fusion, le tri à bulles, le tri par insertion,...., qui ont été élaborés et constamment améliorés au cours du temps.

Le but sera d'en découvrir et d'en coder quelques uns en Python, en s'inspirant dans un premier temps de la méthode que l'on utiliserait spontanément "à la main" lorsque l'on veut trier une série de cartes par exemple.

1. Chercher le maximum / le minimum

Avant de trier, intéressons-nous à un problème dont la solution nous servira par la suite, la recherche du plus grand ou plus petit élément d'une série de données.

Recherche à la main

Travail à faire sur table

Programmation de l'algorithme

Travail à faire sur PC

  1. Re-mélanger vos cartes; commencer à écrire un script Python qui définisse tout d'abord une liste contenant les valeurs de vos cartes mélangées.

    Cliquer ici pour une présentation des listes et leur manipulation

  2. Poursuivre l'écriture du script pour coder la méthode de détermination du maximum et du minimum dans cette liste, dont vous avez établi précédemment l'algorithme.

  3. Vérifier bien entendu à l'exécution que votre script fonctionne correctement !!

SOLUTION

2. Tri dans une liste

Travail à faire sur table

Programmation de l'algorithme

Travail à faire sur PC

  1. Pour ce travail, recréer une liste contenant les valeurs de vos cartes mélangées.

  2. Poursuivre l'écriture du script pour coder la méthode de tri dont vous avez établi précédemment l'algorithme.

  3. Vérifier bien entendu à l'exécution que votre script fonctionne correctement !!

Vous aurez peut-être besoin dans votre script d'arrêter l'exécution d'une boucle avant sa fin "normale"; utilisez pour cela l'instruction :

	break				
				

SOLUTION

3. D'autres algorithmes...

L'algorithme que vous venez de coder s'appelle tri par insertion; comme indiqué ci-dessus, il en existe de nombreux autres. En voici deux autres exemples.

Algorithme 2

  1. L'algorithme parcourt le tableau, et compare les couples d'éléments successifs. Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés.
  2. Après chaque parcours complet du tableau, l'algorithme recommence l'opération.
  3. Lorsqu’aucun échange n'a eu lieu pendant un parcours, cela signifie que le tableau est trié. On arrête alors l'algorithme.

Pour ceux qui auraient du mal à visualiser cet algorithme, voici une autre représentation peut être plus claire...


Algorithme 3

  1. L'algorithme parcourt le tableau, recherche le plus petit élément puis l'échange avec le premier élément du tableau.
  2. Il recommence ensuite la même opération avec le tableau réduit de son premier élément.
  3. Quand on arrive à la fin du tableau, l'algorithme est terminé.

Travail à réaliser

L'objectif est de comparer la rapidité des trois algorithme précédents. Pour cela, vous devez récupérer le fichier Python algo_tri.py et compléter la partie concernant les trois algorithmes de tri : celui que vous avez déjà écrit, et ceux correspondant au deuxième et troisième algorithme.
Vous pourrez alors comparer la rapidité d'exécution de ces trois algorithmes.

N'hésitez pas à vous resservir du jeu de cartes pour mieux visualiser chacun de ces deux autres algorithmes !

SOLUTION