IFT2810

Automne 2008

Algorithmes de tri

Le tri d’un ensemble de données est l’une des taches les plus courantes en informatique.
Il existe plusieurs algorithmes connus de tri. Certains ont une complexité en O(n2 ). Le plus
efficace (quick sort) a une complexité en O(n log2 (n)). Ces algorithmes peuvent être utilisés,
soit pour trier des éléments en ordre croissant, soit en ordre décroissant. Si l’ordre n’est pas
spécifié, alors l’ordre croissant est considéré par défaut.

1 Tri par insertion

C’est l’un des algorithmes les plus utilisés pour le tri. Imaginez une main de carte. À
chaque fois que le joueur prend une nouvelle carte, il l’introduit dans sa main de telle sorte
qu’elle reste ordonnée. Le tri par insertion est basé sur cette idée d’insertion dans une liste
ordonnée.
La liste à trier est divisée en deux : la partie gauche est triée, et la partie droite est
non-triée. À chaque passage, le premier élément de la partie non-triée est introduite dans la
partie triée, de telle sorte que cette dernière reste triée. Pour une liste de n éléments, n − 1
passages sont nécessaires. La complexité de l’algorithme est donc en O(n2 ).
Dans l’algorithme suivant, on considère que les indices d’un tableau commencent à 0, i.e.
le premier élément de la liste est à l’indice 0. “dernier” est l’indice du dernier élément du
tableau.

Algorithme triInsertion (liste <tableau>, dernier <entier>)

1. Pour (courant := 1 a dernier) Faire
2. element := liste[courant] ;
3. parcours := courant-1 ;
4. Tant que (parcours ≥ 0 Et element < liste[parcours]) Faire
5. liste[parcours+1] := liste[parcours] ;
6. parcours := parcours-1 ;
7. Fin Tant que
8. liste[parcours + 1] := element ;
9. Fin Pour

L’algorithme triInsertion contient deux boucles. La boucle 1 parcourt le tableau du

début à la fin. Elle est donc exécutée n fois. La boucle 4 parcourt la première partie triée du
tableau. Dans le pire des cas, toute la première partie de tableau est parcourue. Dans le cas
moyen, la moitié de la première partie de tableau est parcourue.
La complexité dans le pire des cas du tri par insertion est décrit par la fonction f (n) =
n+1
n( 2 ). C’est donc un algorithme en O(n2 ).

1
Avantages du tri par insertion : Méthode naturelle, facile à programmer. De plus, la
méthode est d’autant plus rapide que la liste à triée est presque ordonnée : la méthode est
plus efficace pour une liste presque triée que pour une liste dans un ordre aléatoire.

Structure de données : Méthode aussi efficace si la liste à triée est représentée par un
tableau ou par une liste chaı̂née.

2 Tri par sélection

Un désavantage du tri par insertion est que, même si une liste est presque triée, l’intro-
duction d’un nouvel élément dans cette liste peut nécessiter le mouvement de la plupart des
éléments de la liste. Si la liste à trier est très grande, ce mouvement de tous les éléments à
chaque introduction d’un nouvel élément dans la liste peut être très coûteux. Il serait sou-
haitable de pouvoir immédiatement placer un élément à sa place finale. C’est l’avantage du
tri par sélection.
La liste à trier est divisée en deux : la partie gauche est triée, et la partie droite est
non-triée. De plus, tous les éléments de la partie gauche sont plus petits (ou égaux) que les
éléments de la partie droite. À chaque passage, l’élément minimal de la partie non-triée est
échangé avec la premier élément de la liste non-triée. Ainsi, la liste triée croı̂t de 1 élément.
Pour une liste de n éléments, n − 1 passages sont nécessaires. La complexité de l’algorithme
est donc en O(n2 ).

Algorithme triSelection (liste <tableau>, dernier <entier>)

1. Pour (courant := 0 a dernier) Faire
2. plusPetit := courant ;
3. Pour (parcours := courant+1 a dernier) Faire
4. Si (liste[parcours] < liste[plusPetit])
5. plusPetit := parcours ;
6. Fin Si
7. Fin Pour
8. temp := liste[courant] ;
9. liste[courant] := liste[plusPetit] ;
10. liste[plusPetit] := temp ;
11. Fin Pour

Structure de données : La méthode est appropriée si la liste est représentée par un

tableau. Pas appropriée si la liste est représentée par une liste chaı̂née.

2
3 Tri par échange
3.1 Tri à bulles
La liste à trier est divisée en deux : la partie gauche est triée, et la partie droite est
non-triée. On effectue au plus n − 1 passages. À chaque passage, l’élément minimal de la
partie non-triée se retrouve échangé avec la premier élément de la liste non-triée. Ainsi, la
liste triée croı̂t de 1 élément. La différence entre le tri à bulles et le tri par sélection, est
que le tri à bulle compare chaque paire (u,v) de cases consécutives du tableau non trié en
commençant par la fin du tableau. À chaque fois que u > v, u et v sont échangés. De ce
fait, à la fin d’un passage, on est sûr que le plus petit élément de la partie non-triée sera au
début de cette partie. Le fait de comparer chaque paire de cases consécutives permet de faire
moins de passages que le tri par sélection : si au cours d’un passage aucun échange n’a été
effectué, alors la liste est triée et on s’arrête. La complexité dans le pire des cas est toujours
O(n2 ), mais d’un point de vue pratique, le tri à bulles est plus rapide.

Algorithme triBulles (liste <tableau>, dernier <entier>)

1. courant := 0 ;
2. trie := faux ;
3. Tant que (courant ≤ dernier Et trie=faux) Faire
4. trie := vrai ;
5. Pour (parcours:=dernier a courant+1) Faire
6. Si (liste[parcours] < liste[parcours-1])
7. trie := faux ;
8. echange (liste, parcours, parcours-1) ;
9. Fin Si
10. Fin Pour
11. courant := courant+1 ;
12. Fin Pour

3.2 Quicksort
C’est un tri par échange plus efficace que le tri à bulles. Le problème de ce dernier est
qu’il faut un grand nombre d’échanges pour placer un élément à la bonne place. Quicksort
nécessite moins d’échanges.
À chaque étape, l’algorithme sélectionne un élément particulier du tableau : le pivôt. Le
tableau est alors divisé en trois parties : les éléments plus petits que le pivôt, le pivôt, et les
éléments plus grands que le pivôt. Autrement dit, le pivôt est placé à sa bonne position. On
recommence ensuite, récursivement, pour la partie gauche et la partie droite du tableau.
On pourrait prendre comme élément pivôt le premier, le dernier, ou tout autre élément
du tableau, et ensuite le placer à la bonne position. En général c’est l’élément du milieu qui
est sélectionné, et permuté avec les éléments de début et de fin.
Ici on suppose, par simplicité, que le pivôt est le premier élément de la liste. Pour illustrer
la méthode, considérons la liste :

3
 75 70 65 84 98 78 100 93 55 61 81 68

On veut placer le pivôt (75) à sa place finale dans la liste. À cette étape tout ce qu’on
veut c’est avoir les éléments plus petit que le pivôt avant le pivôt, et les éléments plus grands
après. On effectue les étapes suivantes :
– On parcourt la liste de gauche à droite à partir du pivôt à l’indice l, et on s’arrête dès
qu’on arrive à un indice i contenant une valeur plus grande que le pivôt ;

75 |l 70 65 84 |i 98 78 100 93 55 61 81 68 |r

– On parcours le tableau de droite à gauche et on s’arrête dès qu’on arrive à un indice j

contenant une valeur plus petite que le pivôt ;

75 |l 70 65 84 98 78 100 93 55 61 81 68|j |r

– On échange les valeurs aux indices i et j. Les deux parties du tableau, de 1 à i, et de

j à r sont “correctes : i.e. tous les éléments de la 1ère partie sont plus petits que le
pivôt, et tous les éléments de la deuxième partie sont plus grands que le pivôt.

75 70 65 68 |l 98 78 100 93 55 61 81 |r 84

– On refait la même chose dans le sous-tableau [l + 1..r − 1].

75 70 65 68 |l 98 78 100 93 55 61 81 |r 84

75 70 65 68 61 |l 78 100 93 55 |r 98 81 84

75 70 65 68 61 |l 78 100 93 55 |r 98 81 84

75 70 65 68 61 55 |l 100 93 |r 78 98 81 84

75 70 65 68 61 r 55 |l 100 93 |r 78 98 81 84

– Lorsque les deux pointeurs gauche et droit se retrouvent à la même place ou se croisent,
il ne reste plus qu’à placer le pivôt à la bonne place par un simple échange.

55 70 65 68 61 75 100 93 78 98 81 84

Knuth a montré que cette procédure est efficace pour des listes suffisemment longues.
Lorsque les listes à trier sont courtes (moins que 16 éléments), il est plus efficace d’utiliser
le simple tri par insertion. Cependant, il faut généraliser ce dernier algorithme pour trier un
sous-tableau quelconque, ne commençant pas forcément à l’indice 0. La généralisation est
décrite ci-dessous.

4
Algorithme quickInsertion (liste <Tableau>, premier <entier>, dernier <entier>)
premier et dernier sont les deux indices définissants le sous-tableau de liste à trier

1. Pour (courant := premier +1 a dernier) Faire

2. element := liste[courant] ;
3. parcours := courant -1 ;
4. Tant que (parcours >= premier Et element < liste[parcours]) Faire
5. liste[parcours+1] := liste[parcours] ;
6. parcours := parcours-1 ;
7. Fin Tant que
8. liste[parcours+1] := element ;
9. Fin Pour

Nous avons maintenant tous les éléments pour décrire l’algorithme Quicksort récursif.

5
 Algorithme quickSort (liste <Tableau>, gauche <entier>, droit <entier>)

Si liste trop courte, utiliser le tri par insertion

1. Si (droit - gauche <= tailleMin)
2. quickInsertion (liste, gauche, droit) ;
3. Sinon
4. pivot := liste[gauche] ;
5. triGauche := gauche+1 ;
6. triDroit := droit ;
7. Tant que (triGauche <= triDroit)
8. Tant que (liste[triGauche]<pivot)
9. triGauche := triGauche+1 ;
10. Fin Tant que
11. Tant que (liste[triDroit]>=pivot)
12. triDroit := triDroit-1 ;
13. Fin Tant que
14. Si (triGauche <= triDroit)
15. echange(liste, triGauche, triDroit) ;
16. triGauche := triGauche+1 ;
17. triDroit := triDroit-1 ;
18. Fin Si
19. Fin Tant que
Placer le pivot a la bonne place
20. liste[gauche] := liste[triGauche - 1] ;
21. liste[triGauche-1] := pivot ;
Recursions dans les deux parties du tableau
22. Si (gauche < triDroit)
23. quickSort(liste, gauche, triDroit-1) ;
24. Fin Si
25. Si (triGauche < droit)
26. quickSort(liste, triGauche, droit) ;
27. Fin Si
28. Fin Si

Chaque passage dans la boucle 8. a une complexité proportionnelle à la taille du tableau

à trier. Si le pivot est bien choisit (situé à peu près au milieu du tableau), la taille du tableau
est divisée par deux à chaque étape. La complexité moyenne de l’algorithme est donc en
O(n log2 n). Par contre, la complexité dans le pire des cas est en O(n2 ).

Choix du pivôt : Le choix du premier élément comme pivôt est correct si on a affaire à
une liste aléatoire. Si la liste est “presque triée” ou “presque triée dans le sens inverse”, alors
un meilleur choix est de prendre l’élément du milieu.

6
4 Tri par fusion
C’est une autre méthode “diviser pour reigner”. Comme pour Quicksort, la liste à trier
est subdivisée en deux parties. Chaque partie est triée séparément, et ensuite fusionnée.
Contrairement à Quicksort, la partie “subdivision en deux parties” est directes : on prend
simplement le milieu de la liste. C’est la fusion qui demande plus de travail.
La procédure récursive du tri par fusion est décrite ci-dessous :
triFusion(tableau)
Si tableau a au moins deux éléments
subdiviser le tableau en deux sous-tableaux T1 , T2 ;
triFusion(T1 ) ;
triFusion(T2 ) ;
fusion(T1 , T2 ) ;
La fusion de deux sous-tableaux triés se fait de telle sorte que le tableau résultat soit trié.
Dans l’algorithme suivant, les deux tableaux à fusionner sont T1 et T2 , et le tableau résultat
est T . n1 , n2 sont respectivement le nombre d’éléments de T1 et T2 .

Algorithme fusion (T, T1 , T2 , n1 , n2 )

1. i = i1 = i2 = 0 ;
2. Tant que (i1 < n1 et i2 < n2 )
3. Si (T1 [i1 ] < T2 [i2 ])
4. T [i] = T1 [i1 ] ;
5. i1 = i1 + 1 ;
6. Sinon
7. T [i] = T2 [i2 ] ;
8. i2 = i2 + 1 ;
9. Fin Si
10. i = i + 1;
11. Fin Tant que
12. Si (i1 < n1 − 1)
13. Pour (j = i1 a n1 − 1) Faire
14. T [i] = T1 [j] ;
15. i = i + 1;
16. Fin Pour
17. Sinon Si (i2 < n2 − 1
18. Pour (j = i2 a n2 − 1) Faire
19. T [i] = T2 [j] ;
20. i = i + 1;
21. Fin Pour
22. Fin Si

Plutôt que de passer trois tableaux en paramètres de fusion, il suffit de passer le tableau
initial, et deux indices indiquant le début et la fin du sous-tableau à trier. On a quand même
besoin, dans ce cas, d’un tableau intermédiaire, déclaré comme variable locale.

7
 Algorithme fusion (T , deb, f in)
1. mid = (deb + f in)/2 ;
2. i = 0 ; i1 = deb ; i2 = mid + 1 ;
3. Tant que (i1 < mid et i2 < f in) Faire
4. Si (T [i1 ] < T [i2 ])
5. temp[i] = T [i1 ] ;
6. i1 = i1 + 1 ;
7. Sinon
8. temp[i] = T [i2 ] ;
9. i2 = i2 + 1 ;
10. Fin Si
11. i = i + 1;
12. Fin Tant que
13. Si (i1 < mid)
14. Pour (j = i1 a mid) Faire
15. temp[i] = T [j] ;
16. i = i + 1;
17. Fin Pour
18. Sinon Si (i2 < f in)
19. Pour (j = i2 a f in) Faire
20. temp[i] = T [j] ;
21. i = i + 1;
22. Fin Pour
23. Fin Si
24. Pour (i = deb a f in) Faire
25. T [i] = temp[i] ;
26. Fin Pour

L’algorithme récursif de tri par fusion est le suivant :

Algorithme triFusion (T , deb, f in)

1. Si (deb < f in)
2. mid = (deb + f in)/2 ;
3. triFusion (T , deb, mid) ;
4. triFusion (T , mid + 1, f in) ;
5. fusion (T , deb, f in) ;
6. Fin Si

La complexité de cet algorithme est en O(n log2 (n)).

Structure de donnée : Pour être efficace du point de vue du temps, la procédure de

fusion nécessite un tableau intermédiaire : plus grande complexité en mémoire.

8
 Ce n’est pas le cas si les données sont représentées par des listes chaı̂nées. Dans ce cas,
aucune liste intermédiaire n’est nécessaire, et la complexité en temps du tri par fusion est
toujours en O(n log2 (n)).

5 Résumé
Les méthodes de tri peuvent être subdivisées en quatre classes principales : le tri par
insertion, le tri par sélection (tri par séction direct ou tri par monceaux), le tri par échange
(tri à bulles ou Quicksort), et le tri externe.
Le choix d’une méthode de tri dépend de plusieurs critères :
– La taille de la liste à trier. Si la liste est courte, la méthode la plus simple à programmer
(tri par insertion ou tri par sélection direct) est probablement la plus efficace d’un point
de vue pratique.
– Si la liste est trop longue pour qu’une recherche en O(n2 ) soit efficace, mais assez
courte pour être stockée en mémoire interne, alors on peut choisir Quicksort ou le tri
par fusion.
– Si la liste est représentée par un tableau, on peut utiliser le tri par insertion, le tri par
sélection, ou le tri par échange.
– Si la liste est représentée par une liste chaı̂née, on peut utiliser le tri par insertion ou
le tri par fusion.