1 ALGORITHMES DE TRI DES TABLEAUX ASD2

ALGORITHMES DE TRI DES TABLEAUX

I. Introduction
Un algorithme de tri permet d’ordonnée les données dans un tableau, une liste ou un fichier
selon un critère bien déterminé dans ordre croissant ou décroissant. L’objectif principal de
tri des données est de faciliter et minimiser le temps de recherche. Par exemple, si on a un
tableau contenant mille réelles et on veut vérifier l’existence ou non d’un élément, il sera
plus difficile de trouver cet élément si le tableau n’est pas trié puisque nous allons effectuer
une recherche exhaustive. Par contre, si le tableau est trié le temps de recherche sera moins
important puisque on peut faire des sauts pour localiser rapidement l’élément en utilisant
par exemple une recherche dichotomique.

Il existe plusieurs algorithmes de tri dont la différence réside principalement dans le temps
d’exécution exprimé par ce qu’on appelle la complexité algorithmique du programme.
Egalement, on peut les distinguer par leurs stabilités. Un algorithme de tri est stable s’il ne
modifie pas l'ordre initial des éléments égaux. Un algorithme de tri est instable s’il modifie
l'ordre initial des éléments égaux.

La figure ci-dessous illustre quelques algorithmes de tri très connus.

Tri

Insertion Sélection Bulle Fusion Shell Rapide

Gnome Shaker Peigne

1|Page
1 ALGORITHMES DE TRI DES TABLEAUX ASD2

Dans ce cours nous allons s’intéressé aux trois types les plus simples qui sont : le tri par sélection, le
tri par insertion et le tri à bulle.

II. Le tri par sélection

L’algorithme de tri par sélection consiste à chercher le plus petit élément du tableau puis le
permuter avec le premier élément du tableau, puis faire la même chose mais permuter le
petit élément avec le deuxième élément du tableau et ainsi de suite jusqu’à terminer tous le
tableau. Il existe une autre méthode de tri par sélection qui utilise un autre tableau comme
résultat. Donc au lieu de permuter avec le premier élément du tableau, il suffit de copier le
minimum dans l’autre tableau et ainsi de suite mais toute en remplaçant la valeur du
minimum par la valeur maximale dans le tableau original.

On a le tableau suivant contenant cinq entier et on veut le trié en utilisant le tri par
sélection. La case en rouge indique le minimum qu’on va permuter avec l’élément courant.
La flèche en bleu indique l’élément courant.

 Méthode avec la permutation

Itération n°1 10 3 1 5 9 permutation

Itération n°2 1 3 10 5 9 Pas de permutation

Itération n°3 1 3 10 5 9 permutation

Itération n°4 1 3 5 10 9 permutation

Fin 1 3 5 9 10

2|Page
1 ALGORITHMES DE TRI DES TABLEAUX ASD2

 Méthode avec un autre tableau

La case en vert indique le changement du minimum par le maximum du tableau pour ne pas
être considéré dans la prochaine recherche.

Itération n°1 10 3 1 5 9 1

Itération n°2 10 3 10 5 9 1 3

Itération n°3 10 10 10 5 9 1 3 5

Itération n°4 10 10 10 10 9 1 3 5 9

Itération n°5 10 10 10 10 10 1 3 5 9 10

Le pseudo-code de l’algorithme de tri par sélection en utilisant la méthode de permutation

est écrit comme suit sachant que n est le nombre d’élément du tableau:

Procédure Tri_Selection(var T : tableau, n : entier)

i,min : entier
Début
Pour i de 0 à n - 2
min  MinTab(T,i,n) // donner la position du minimum
Si min <> i alors
permutTab(T,i,min)
Fin si
Fin pour
Fin procédure
//------------------------------------------------------------------
Fonction MinTab(T : tableau, i : entier, n : entier) retourne entier
min,j : entier
Début
Min  i
Pour j de i+1 à n-1
si T[j]<T[min] alors
min  j
3|Page
1 ALGORITHMES DE TRI DES TABLEAUX ASD2

Fin si
Fin pour
MiniTab  min
Fin fonction
//------------------------------------------------------------------
Procédure PermutTab(var T : tableau, i : entier, j : entier)
bf : type de l’élément
Début
Bf  T[i]
T[i]  T[j]
T[j]  bf
Fin procédure

III. Le tri par insertion

Le tri par insertion consiste à prendre l’ième élément du tableau et chercher sa bonne
position puis effectuer un décalage jusqu’à cette position puis l’insérer. Dans ce qui suit une
exécution manuelle de l’algorithme. On a un tableau de cinq entiers, l’algorithme commence
par l’indice 1 puis cherche la bonne position de cet élément toute en sauvegardant sa valeur
en dehors du tableau. Puis effectuer une série de décalage jusqu’à la bonne position dans la
laquelle l’élément va être insérer et ainsi de suite.

Elem

Itération n°1 10 3 1 5 2 3 Décalage de {10}

Itération n°2 3 10 1 5 2 1 Décalage de {3,10}

Itération n°3 1 3 10 5 2 5 Décalage de {10}

Itération n°4 1 3 5 10 2 2 Décalage {3,5,10}

Fin 1 2 3 5 10

Le pseudo-code de la méthode de tri par insertion est écrit comme suit sachant que n est le
nombre des éléments du tableau.

4|Page
1 ALGORITHMES DE TRI DES TABLEAUX ASD2

Procédure Tri_Insertion(var T : tableau, n : entier)

i : entier
Début
Pour i de 1 à n - 1
Décalage(T,i,n)
Fin pour
Fin procédure
//------------------------------------------------------------------
Procédure Décalage(var T : tableau, i : entier)
j : entier
elem : type de l’élément
Début
elem  T[i]
j  i-1
Tant que j>=0 et elem<T[j]
T[j+1]  T[j]
j  j-1
Fin tant que
T[j+1]  elem
Fin fonction

IV. Le tri à bulle

Le tri à bulle consiste à comparer les éléments consécutifs deux à deux du tableau puis faire
des permutations puis répéter l’opération dès le début. L’algorithme s’arrête lors qu’il n’y
aura plus de permutation. Dans l’exemple qui suit on décrit l’exécution de l’algorithme de tri
à bulle. Le bleu indique qu’il y a une permutation entre les éléments et le vert indique qu’il
n’y a pas de permutation.

Itération n°1 i=0 10 3 1 5 9 Permut=vrai

Itération n°2 i=1 3 10 1 5 9 Permut=vrai

Itération n°3 i=2 3 1 10 5 9 Permut=vrai

Itération n°4 i=3 3 1 5 10 9 Permut=vrai

Itération n°5 i=0 3 1 5 9 10 Permut=vrai

5|Page
1 ALGORITHMES DE TRI DES TABLEAUX ASD2

Itération n°6 i=1 1 3 5 9 10

Itération n°7 i=2 1 3 5 9 10

Itération n°8 i=3 1 3 5 9 10

Itération n°9 i=0 1 3 5 9 10 Permut=faux

Itération n°10 i=1 1 3 5 9 10

Itération n°11 i=2 1 3 5 9 10

Itération n°12 i=3 1 3 5 9 10 Fin

Le pseudo-code de la méthode de tri à bulle est écrit comme suit sachant que n est le
nombre des éléments du tableau.

Procédure Tri_Bulle(var T : tableau, n : entier)

permut : booléen
i : entier
Début
permut  vrai
i=0
Tant que permut=vrai
permut  faux
Pour i=0 à n-2
Si T[i]>T[i+1] alors
PermutTab(T,i,i+1)
permut  vrai
Fin si
Fin pour
Fin tant que
Fin procédure
6|Page
1 ALGORITHMES DE TRI DES TABLEAUX ASD2

//------------------------------------------------------------------
Procédure PermutTab(var T : tableau, i : entier, j : entier)
bf : type de l’élément
Début
bf  T[i]
T[i]  T[j]
T[j]  bf
Fin procédure

7|Page