Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapter 06 - Sort algorithms

Généralités

Dans cette partie nous allons poser la question du tri d'une liste de données.

But des algorithmes de tri

Le problème auquel nous allons nous confronter est très simple à comprendre : à partir d’une liste de données numériques, réordonner ces valeurs par ordre croissant.

Tout sous-programme résolvant ce problème sera naturellement une procédure, il n'y a pas lieu ici de calculer une valeur à retourner. La liste à trier en sera alors un paramètre qui sera lu et modifié.

[Note]

Les implémentations en Python des divers algorithmes de tri que nous allons présenter respecteront sans problèmes ce qui précède, car rappelons-le les listes sont des types de données muables. Elles pourront donc être modifiées par nos procédures de tri.

Pour des raisons évidentes d'optimisation de la mémoire utilisée, nos tris se feront "sur place", c'est-à-dire que nous n'utiliserons pas de listes intermédiaires pour stocker provisoirement les valeurs.

Il s’agit d’un des plus problèmes les plus classiques de l’algorithmique. De nombreuses résolutions en sont possibles avec des méthodes radicalement différentes.

[Note]

Les lecteurs les plus acharnés pourront consulter la série de livres de Donald Knuth “The Art of Computer Programming” où plus d’une trentaine d’algorithmes de tri sont étudiés en détail.

Nous serons quand à nous plus modestes, nous n'en étudierons que cinq.

[Note]

La comparaison de l'efficacité de ces différentes procédures de tri sera faite lors de l'étude de la théorie de la complexité algorithmique dans le cours 2ADS.

Méthodes utilisées

Nous étudierons dans ce chapitre deux types d'algorithmes de tri :

  • Des algorithmes itératifs

  • Des algorithmes récursifs, basés sur le paradigme “diviser pour régner”, dans lesquels le tri d’une liste s’effectuera en la divisant plusieurs fois par deux jusqu’à obtention de sous-listes ne comportant qu’une seule valeur.

[Note]

Dans ce chapitre de cours on se contentera juste de décrire les algorithmes et de les appliquer sur des exemples.

Le travail d’implémentation de ces algorithmes en Python sera fait lors de la séance d'exercices correspondante.

Algorithmes itératifs

On va présenter dans cette partie les trois algorithmes de tri itératifs les plus connus.

Tri par sélection

Le tri par sélection est assez intuitif du point de vue mathématique, puisqu'il consiste dans un premier temps à mettre à la première place le plus petit élément de la liste, puis à la seconde place le deuxième plus petit élément, etc.

En voici sa description précise :

  1. Rechercher dans la liste la plus petite valeur et la permuter avec le premier élément de la liste.

  2. Rechercher ensuite la plus petite valeur à partir de la deuxième case et la permuter avec le second élément de la liste.

  3. Et ainsi de suite jusqu’à avoir parcouru toute la liste.

Example 1.1. Déroulement du tri par sélection sur un exemple

On considère la liste suivante de cinq entiers :

Première itération :

  • On détermine le minimum des éléments de la liste :

  • Et on le permute avec le premier élément de la liste :

[Note]

Code couleur : en noir figurent les éléments déjà triés et en rouge le minimum de ceux à trier.

Seconde itération :

  • On détermine le minimum des éléments de la liste à partir de la deuxième case :

  • Et on le permute avec le second élément de la liste :

Troisième itération :

  • On détermine le minimum des éléments de la liste à partir de la troisième case :

  • Et on le permute avec le troisième élément de la liste :

Quatrième itération :

  • On détermine le minimum des éléments de la liste à partir de la quatrième case :

  • Et on le permute avec le quatrième élément de la liste :

Le cinquième et dernier élément la liste est de fait à sa place, le tri est terminé :


Tri à bulles

Le tri à bulles consiste à parcourir toute la liste en comparant chaque élément avec son successeur, puis en les remettant dans le "bon" ordre si nécessaire. Et à recommencer si besoin est.

En voici sa description précise :

  1. Parcourir la liste en comparant chaque élément avec son successeur.

  2. Si ce dernier est le plus petit des deux, les permuter.

  3. Si lors du parcours de la liste une permutation au moins a été effectuée, recommencer un nouveau parcours.

Example 1.2. Déroulement du tri à bulles sur un exemple

On considère la liste suivante de cinq entiers :

Première itération :

  • On compare 5 et 8 :

  • Ils sont dans l'ordre, donc on ne les permute pas :

[Note]

Code couleur : en rouge figurent les deux éléments que l'on est en train de comparer.

  • On compare 8 et 2 :

  • On les permute pour les mettre dans l'ordre :

  • On compare 8 et 9 :

  • Ils sont dans l'ordre, donc on ne les permute pas :

  • On compare 9 et 5 :

  • On les permute pour les mettre dans l'ordre :

[Note]

Le lecteur constatera qu’à la fin de la première itération le plus grand élément de la liste se trouve à sa place, c’est-à-dire en dernière position.

Cela implique qu'à la fin de la seconde itération, il sera inutile de comparer les deux derniers éléments de la liste.

Seconde itération :

  • On compare 5 et 2 :

  • On les permute pour les mettre dans l'ordre :

  • On compare 5 et 8 :

  • Ils sont dans l'ordre, donc on ne les permute pas :

  • On compare 8 et 5 :

  • On les permute pour les mettre dans l'ordre :

Troisième itération : On parcourt de nouveau la liste, mais cette fois-ci on constate qu’il n’y a plus de permutations à effectuer.

On n'effectue donc pas de quatrième itération, la liste est triée :


Tri par insertion

Le tri par insertion est celui naturellement utilisé par les joueurs de cartes pour trier leur jeu. Il consiste à insérer les éléments un par un en s'assurant que lorsque l'on rajoute un nouvel élément, les éléments déjà insérés restent triés.

En voici sa description précise :

  1. Considèrer le premier élément de la liste. A lui tout seul il constitue une liste triée.

  2. Insérer ensuite le second élément de telle sorte que les deux premiers éléments soient triés.

  3. Continuer ainsi en insérant sucessivement chaque élément à sa “bonne” place dans la partie déjà triée de la liste.

[Note]

Cette insertion se fait en décalant certaines des valeurs déjà triées. Comme on va le voir sur un exemple.

Example 1.3. Déroulement du tri par insertion sur un exemple

On considère la liste suivante de cinq entiers :

Insertion du second élément vis-à-vis du premier :

  • On considère la valeur 3 :

  • Que l’on retire provisoirement de la liste :

  • On décale le 5 :

  • Et on réinsère la valeur 3 :

[Note]

Code couleur : en noir figurent les éléments déjà triés et en rouge celui que l’on est en train d'insérer.

Insertion du troisième élément vis-à-vis des deux premiers :

  • On considère la valeur 1 :

  • Que l’on retire provisoirement de la liste :

  • On décale le 3 et le 5 :

  • Et on réinsère la valeur 1 :

Insertion du quatrième élément vis-à-vis des trois premiers :

  • On considère la valeur 4 :

  • Que l’on retire provisoirement de la liste :

  • On décale le 5 :

  • Et on réinsère la valeur 4 :

Insertion du cinquième élément vis-à-vis des quatre premiers :

  • On considère la valeur 2 :

  • Que l’on retire provisoirement de la liste :

  • On décale le 3, le 4 et le 5 :

  • Et on réinsère la valeur 2 :

Chaque élément a été inséré à sa place, le tri est terminé :


[Note]

Lors de l'implémentation de cet algorithme, le terme "retirer" utilisé dans l'exemple précédent signifiera "mémoriser provisoirement dans une variable".

Algorithmes récursifs

On va présenter dans cette partie les deux algorithmes de tri récursifs les plus connus. Ils utilisent tous les deux le paradigme diviser pour régner présenté dans le précédent chapitre de ce cours.

Tri fusion

Le tri fusion consiste à trier récursivement les deux moitiés de la liste, puis à fusionner ces deux sous-listes triées en une seule. La condition d’arrêt à la récursivité sera l’obtention d'une liste à un seul élément, car une telle liste est évidemment déjà triée.

Voici donc les trois étapes (diviser, régner et combiner) de cet algorithme :

  1. Diviser la liste en deux sous-listes de même taille (à un élément près) en la "coupant" par la moitié.

  2. Trier récursivement chacune de ces deux sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.

  3. Fusionner les deux sous-listes triées en une seule.

Example 1.4. Déroulement du tri fusion sur un exemple

On considère la liste suivante de sept entiers :

On la scinde en deux sous-listes en la coupant par la moitié :

Sous-listes que l’on scinde à leur tour :

Sous-listes que l’on scinde à leur tour :

Ces sous-listes sont triées car elles n’ont qu’un élément. On va maintenant les fusionner deux par deux en de nouvelles sous-listes triées :

De nouveau une étape de fusionnnement :

Une dernière fusion :

On a fusionné toutes les sous-listes obtenues lors des appels récursifs, le tri est terminé :


[Note]

Lors de l'implémentation de cet algorithme, toute la difficulté résidera bien sûr dans la mise au point de cette étape de fusionnement.

Tri rapide

Le tri rapide consiste à positionner un par un par les éléments à leur place définitive en ne laissant à leur gauche que des éléments plus petits et à leur droite que des éléments plus grands. Les deux sous-listes obtenues par ce positionnement sont ensuite traitées de la même façon par récursivité. La condition d’arrêt à la récursivité sera l’obtention d'une liste à un seul élément, car cet unique élément est nécessairement au "bon" endroit.

[Note]

De par sa nature, ce tri ne comporte pas la phase "combiner" théoriquement présente dans les algorithmes de type diviser pour régner.

Voici donc les trois étapes (diviser, régner et combiner) de cet algorithme :

  1. Considérer le premier élément de la liste et le positionner à sa place définitive, avec à sa gauche une sous-liste constituée d’éléments qui lui sont inférieurs ou et égaux et à sa droite une sous-liste constituée d’éléments qui lui sont strictement supérieurs.

  2. Appliquer récursivement ce même traitement aux deux sous-listes ainsi obtenues. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.

  3. Pas de résultats à combiner.

Example 1.5. Déroulement du tri rapide sur un exemple

On considère la liste suivante de huit entiers :

Lors du premier appel récursif, on va positionner le premier élément, à savoir 7, à sa place définitive. Pour faire cela, on va mettre à sa gauche les éléments de la liste qui lui sont inférieurs ou égaux, et à sa droite ceux qui lui sont strictement supérieurs :

[Note]

Code couleur : en noir figurent les éléments déjà placés et en rouge ceux que l’on va placer à cet appel de la procédure.

Lors du second appel récursif, selon le même principe on va placer les éléments 4 et 10 qui sont les premiers éléments des sous-listes créées lors de l'appel précédent :

Le placement des éléments 4 et 10 s'est fait à l’intérieur des deux sous-listes délimitées par l'élément 7. On voit bien ici le côté récursif de cet algorithme, puisque l’on applique le même traitement aux deux sous-listes qu’à la liste initiale.

Lors du troisième appel récursif, on va placer les éléments 2, 5 et 14 qui sont les premiers éléments des sous-listes créées lors de l'appel précédent :

Lors du quatrième appel récursif, on va placer les éléments 12 et 16 qui sont les premiers éléments des sous-listes créées lors de l'appel précédent :

Chaque élément a été positionné à sa place, le tri est terminé :


[Note]

Dans ce contexte, l'élément que l'on positionne à sa place définitive est appelé pivot. Le choix effectué ici est de prendre pour pivot le premier élément de la liste.

Cet choix est le plus simple mais il n'est pas optimal. Le lecteur curieux pourra se demander quel autre pivot on aurait pu prendre pour améliorer les performances de cet algorithme.

About SUPINFO | Contacts & addresses | Teachers | Press | INVESTOR | Conditions of Use & Copyright | Respect of Privacy
Logo de la société Cisco Logo de la société IBM Logo de la société Sun-Oracle Logo de la société Apple Logo de la société Sybase Logo de la société Novell Logo de la société Intel Logo de la société Accenture Logo de la société SAP Logo de la société Prometric Logo du IT Academy Program par Microsoft

SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels
and is accredited in France by Association Ecole Supérieure d'Informatique de Paris (ESI SUPINFO)