Chapitre 3

Algorithmes de tri

Trier un ensemble d’objets consiste à les ordonner en fonction d’une relation

d’ordre définie sur ces objets. Souvent, les objets sont indexés par une clé et
la relation d’ordre porte sur cette clé. Par exemple, chaque étudiant inscrit
à l’université d’Aix-Marseille reçoit un numéro qui constitue la clé d’accès à
son dossier. On trie des objets lorsqu’ils sont nombreux et qu’on doit pouvoir
y accéder rapidement : rechercher un élément dans un tableau non trié est
une opération de complexité linéaire dans le nombre d’objets, alors que si le
tableau est trié, la recherche peut être e↵ectuée en temps logarithmique.
On dit qu’un algorithme de tri est
— en place, s’il n’utilise qu’un espace mémoire de taille constante pen-
dant son exécution, (en plus de l’espace servant à stocker les objets
à trier)
— par comparaison, si le tri s’e↵ectue en comparant les objets entre
eux. Lorsque les valeurs prises par ces objets sont peu nombreuses
(par exemple, les années de naissance), il peut être plus efficace de
comparer chaque objet aux valeurs possibles.
— stable s’il préserve l’ordre d’apparition des objets en cas d’égalité des
clés. Cette propriété est utile par exemple lorsqu’on trie successive-
ment sur plusieurs clés di↵érentes. Si l’on veut ordonner les étudiants
par rapport à leur nom puis à leur moyenne générale, on veut que les
étudiants qui ont la même moyenne apparaissent dans l’ordre lexico-
graphique de leurs noms.
Dans ce chapitre, nous étudions
— des tris simples, tri à bulle, tri par insertion, tri par sélection, de
complexité O(n2 ) en moyenne,
— des tris plus sophistiqués, tris par fusion, tri par tas et tri rapide, de

39
40 CHAPITRE 3. ALGORITHMES DE TRI

complexité O(n log n) en moyenne

— et quelques tris particuliers, parfois très efficaces mais pas toujours
applicables, tri par dénombrement et tri par base.
Des travaux pratiques permettront d’étudier expérimentalement et de
comparer la complexité de ces algorithmes.
En général les objets à trier sont stockés dans des tableaux, mais ce n’est
pas toujours le cas. Lorsque les objets sont stockés dans des listes chainées,
on peut soit les recopier au préalable dans un tableau temporaire, soit utiliser
un tri adapté comme le tri par fusion.

3.1 Tri par sélection, tri par insertion, tri à bulle.

Le tri par sélection consiste simplement à sélectionner l’élément le plus
petit de la suite à trier, à l’enlever, et à répéter itérativement le processus
tant qu’il reste des éléments dans la suite. Au fur et à mesure les éléments
enlevés sont stockés dans une pile. Lorsque la suite à trier est stockée dans
un tableau on s’arrange pour représenter la pile dans le même tableau que
la suite : la pile est représentée au début du tableau, et chaque fois qu’un
élément est enlevé de la suite il est remplacé par le premier élément qui
apparaı̂t à la suite de la pile, et prends sa place. Lorsque le processus s’arrête
la pile contient tous les éléments de la suite triés dans l’ordre croissant. Le
tri par sélection est en ⇥(n2 ) dans tous les cas.

Algorithme 12: TriParSelection

entrée : T [1, n] est un tableau d’entiers, n 1.
résultat : les éléments de T sont ordonnés par ordre croissant.
début
pour i := 1 à n 1 faire
j := IndMin(T [i, n]) # indice du plus petit élément de T [i, n]
permuter T [i] et T [j]

Exercice 1 Quel est l’invariant du tri par sélection ? La complexité de

l’algorithme dépend-elle des données d’entrée ? Pourquoi la complexité est-
elle quadratique dans tous les cas ?

Le tri par insertion consiste à insérer les éléments de la suite les uns
après les autres dans une suite triée initialement vide. Lorsque la suite est
stockée dans un tableau la suite triée en construction est stockée au début
3.1. TRI PAR SÉLECTION, TRI PAR INSERTION, TRI À BULLE. 41

du tableau. Lorsque la suite est représentée par une liste chainée on insère
les maillons les uns après les autres dans une nouvelle liste initialement vide.
Algorithme 13: TriParInsertion<
entrée : T [1, n] est un tableau d’entiers, n 1.
résultat : les éléments de T sont ordonnés par ordre croissant.
début
pour i := 2 à n faire
j := i # indice de l’élément à insérer dans T [1, i 1]
v := T [i] # valeur de l’élément à insérer
tant que j > 1 et v < T [j 1] faire
T [j] := T [j 1] # j 1 est une case libre
j := j 1 # j est une case libre
T [j] := v

Le tri e↵ectue n 1 insertions. A la ième itération, dans le pire des cas,

l’algorithme e↵ectue i 1 recopies. Le coût du tri est donc
n
X n(n 1)
(i 1) = = O(n2 ).
2
i=2

Dans le meilleur des cas le tri par insertion requiert seulement O(n) traite-
ments. C’est le cas lorsque l’élément à insérer reste à sa place, donc quand la
suite est déja triée.On peut montrer que le tri par insertion est quadratique
en moyenne.

Exercice 2 (difficile) On considère toutes les permutations de l’ensemble

Sn = {1, . . . , n}. On veut montrer que le tri par insertion sera quadratique
en moyenne sur l’ensemble de ces permutations.
1. Soit T une permutation de Sn et soient 1  i < j  n.POn définit
Ii,j (T ) = 1 si T [i] > T [j] et Ii,j (T ) = 0 sinon, et I(T ) = i<j Ii,j (T )
(nombre d’inversions dans T ). Montrez que I(T ) est exactement égal
au nombre de fois que l’instruction T [j] := T [j 1] est exécutée par
l’algorithme de tri par insertion.
2. On choisit une permutation T de Sn au hasard, toutes les permuta-
tions ayant la même probabilité. Soit i < j. Ii,j (T ) est une variable
aléatoire. Montrez que son espérance est égale à E(Ii,j (T )) = 1/2.
Montrez que E(I(T )) = n(n 1)/4.
3. Comparez la complexité en moyenne et la complexité dans le pire des
cas. Montrez que la complexité en moyenne est en ⇥(n2 ).
42 CHAPITRE 3. ALGORITHMES DE TRI

Le tri à bulle consiste à parcourir le tableau, tant qu’il n’est pas trié,
et à permuter les couples d’éléments consécutifs mal ordonnés. On sait que
le tableau est trié si lors d’un parcours, aucun couple d’éléments n’a été
permuté.

Algorithme 14: TriBulle

entrée : T [1, n] est un tableau d’entiers, n 1.
résultat : les éléments de T sont ordonnés par ordre croissant.
début
M := n 1
tant que le tableau n’est peut-être pas trié faire
pour i := 1 à M faire
si T [i] > T [i + 1] alors
permuter T [i] et T [i + 1]
M =M 1

Exercice 3 Dans l’algorithme du tri à bulle,

1. montrez qu’après k parcours du tableau (boucle interne), au moins k
éléments sont à leur place,
2. déduisez-en que la complexité dans le pire des cas est en ⇥(n2 ),
3. montrez qu’après chaque parcours, le plus petit élément du tableau
reste à sa place ou recule au plus d’une case,
4. déduisez-en que la complexité moyenne est en ⇥(n2 ) (pour tout entier
1  i  n, avec une probabilité 1/n, l’élément minimal du tableau
est situé à l’indice i),
5. montrez que dans le meilleur des cas, l’algorithme est linéaire,
6. montrez que le tri est stable et identifiez précisément la raison de
cette propriété.

3.2 Tri par fusion et tri rapide

3.2.1 Tri par fusion (ou par interclassement)
Le tri par fusion (merge sort en anglais) implémente une approche de
type diviser pour régner très simple : la suite à trier est tout d’abord scindée
en deux suites de longueurs égales à un élément près. Ces deux suite sont
3.2. TRI PAR FUSION ET TRI RAPIDE 43

ensuite triées séparément avant d’être fusionnées (ou interclassées). L’effica-

cité de ce tri vient de l’efficacité de la fusion : le principe consiste à parcourir
simultanément les deux suites triées dans l’ordre croissant de leur éléments,
en extrayant chaque fois l’élément le plus petit. La fusion peut-être e↵ec-
tuée en conservant l’ordre des éléments de même valeur (le tri par fusion est
stable)
Le tri par fusion est bien adapté aux listes chainées : pour scinder la liste
il suffit de la parcourir en liant les éléments de rangs pairs d’un coté et les
éléments de rangs impairs de l’autre. La fusion de deux listes chainées se fait
facilement. Inversement, si la suite à trier est stockée dans un tableau il est
nécessaire de faire appel à un tableau annexe lors de la fusion, (au moins
dans ses implémentations les plus courantes).

Algorithme 15: TriParFusion

entrée : T [m, n] est un tableau d’entiers, m  n.
résultat : les éléments de T sont ordonnés par ordre croissant.
début
si m < n alors
TriFusion(T [m, b m+n 2 c])
TriFusion(T [b m+n 2 c + 1, n])
Interclassement(T[m, n])

La complexité de l’interclassement est O(n) dans tous les cas. La com-

plexité du tri par fusion vérifie donc l’équation récursive suivante :

T (n) = 2 ⇥ T (n/2) + O(n).

On en déduit que le tri par fusion est en O(n log n).

On le vérifie en cumulant les nombres de comparaisons e↵ectuées à
chaque niveau de l’arbre qui représente l’exécution de la fonction (voir figure
ci-dessous) : chaque nœud correspond à un appel de la fonction, ses fils cor-
respondent aux deux appels récursifs, et son étiquette indique la longueur
de la suite. La hauteur de l’arbre est donc log2 n et à chaque niveau le cumul
des traitements locaux (scission et fusion) est O(n), d’où on déduit un coût
total de O(n) ⇥ log2 n = O(n log n).
44 CHAPITRE 3. ALGORITHMES DE TRI

Algorithme 16: Interclassement

entrée : T [m, n] est un tableau d’entiers, m  n, T [m, b m+n 2 c] et
T [b m+n
2 c + 1, n] sont triés par ordre croissant.
résultat : les éléments de T sont ordonnés par ordre croissant.
début
i := m, j := b m+n 2 c + 1, k := m
tant que i  b m+n 2 c ET j  n faire
si T [i]  T [j] alors
S[k] := T [i], i := i + 1
sinon
S[k] := T [j], j := j + 1
k := k + 1
# un des deux tableaux est vide
tant que i  b m+n 2 c faire
S[k] := T [i], i := i + 1, k := k + 1
# recopie de la fin du premier tableau ; la fin du second est en
place
pour i := m à k 1 faire
T [i] := S[i] # recopie de S dans T

n 2x n

n/2 n/2 2x n

log n
n/4 n/4 n/4 n/4 2x n

n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8

1 1 1 ....

Exercice 4
1. Qu’est-ce qui, dans l’algorithme d’interclassement, garantit la stabi-
lité du tri fusion ?
2. Écrivez l’algorithme de fusion lorsque les données sont stockées dans
une liste chaı̂née.
3.2. TRI PAR FUSION ET TRI RAPIDE 45

3.2.2 Tri rapide

Le tri rapide (quicksort) est une méthode de type diviser pour régner qui
consiste, pour trier un tableau T , à le partitionner en deux sous-tableaux T1
et T2 contenant respectivement les plus petits et les plus grands éléments de
T , puis à appliquer récursivement l’algorithme sur les tableaux T1 et T2 .
Il existe plusieurs méthodes pour partitionner un tableau. Le principe
général consiste à utiliser un élément particulier, le pivot, comme valeur de
partage.
Dans l’algorithme qui suit, le pivot est le premier élément du tableau.
On peut également choisir aléatoirement un élément quelconque du tableau
(voir TD).

L’algorithme partition prend en entrée un tableau T [m, n] (avec m 

n) et réordonne T de façon à
— mettre en début de tableau les éléments T [i] de T [m + 1, n] tels que
T [i]  T [m],
— mettre en fin de tableau les éléments T [i] de T [m + 1, n] tels que
T [i] > T [m],
— placer T [m] entre les deux.
Il retourne l’indice de T [m] dans le nouveau tableau : T [m] s’appelle le pivot.

Algorithme 17: partition

entrée : T [m, n] est un tableau d’entiers.
sortie : l’indice du pivot dans le tableau réarrangé
début
pivot := T [m]
i := m + 1 # indice où insérer le premier élément  T [m]
pour j := m + 1 à n faire
# j est l’indice de l’élément courant
si T [j]  pivot alors
permuter T [i] et T [j]
i := i + 1
permuter T [m] et T [i 1]
retourner i 1

Le QuickSort consiste à partitionner un tableau T [m, n] autour du pivot

T [m] puis à trier récursivement chacune des deux parties T [m, IndP ivot 1]
et T [IndP ivot + 1, n] à l’aide du QuickSort.
46 CHAPITRE 3. ALGORITHMES DE TRI

Algorithme 18: QuickSort

entrée : T [m, n] est un tableau d’entiers.
sortie : T est trié par ordre croissant
début
si m < n alors
IndPivot = partition(T [m, n])
QuickSort(T[m, IndPivot 1])
QuickSort(T[IndPivot + 1, n])

On peut montrer que la complexité du tri rapide est O(n log n) en moyenne,
mais aussi O(n2 ) dans le pire des cas (voir une étude de la complexité en
TD). En pratique, c’est l’algorithme le plus utilisé et très souvent, le plus
rapide.

3.3 Complexité optimale d’un algorithme de tri

par comparaison

L’arbre de décision d’un tri par comparaison représente le comporte-

ment du tri dans toutes les configurations possibles. Les configurations cor-
respondent à toutes les permutations des objets à trier, en supposant qu’ils
soient tous comparables et de clés di↵érentes. S’il y a n objets à trier, il
y a donc n! configurations possibles. On retrouve toutes ces configurations
sur les feuilles de l’arbre, puisque deux permutations initiales distinctes ne
peuvent pas produire le même comportement du tri : en e↵et, dans ce cas le
tri n’aurait pas fait son travail sur un des deux ordonnancements. Chaque
nœud de l’arbre correspond à une comparaison entre deux éléments et a
deux fils, correspondants aux deux ordres possibles entre ces deux éléments.
3.3. COMPLEXITÉ OPTIMALE D’UN ALGORITHME DE TRI PAR COMPARAISON47

1 2 3
a b c
e1 <= e2 <= > e1 > e2

a b c b a c
e2 > e3
<= > e2 <= e3 <= >

a b c a c b b a c b c a

<= > <= >

a c b c a b b c a c b a

Sur la figure ci-dessus nous avons représenté l’arbre de décision du tri

par insertion sur une suite de trois éléments. A la racine de l’arbre le tri
compare tout d’abord les deux premiers éléments de la suite a et b, afin
d’insérer l’élément b dans la suite triée constituée uniquement de l’élément
a. Suivant leur ordre les deux éléments sont permutés (fils droit) ou laissés
en place (fils gauche). Au niveau suivant l’algorithme compare les éléments
de rang 2 et de rang 3 afin d’insérer l’élément de rang 3 dans la suite triée
constituée des 2 premiers éléments, et ainsi de suite. Les branches de l’arbre
de décision du tri par insertion n’ont pas toutes la même longueur du fait que
dans certains cas l’insertion d’un élément est moins coûteuse, en particulier
quand l’élément est déjà à sa place.
Les feuilles de l’arbre représentent toutes les permutations du tableau
en entrée. Puisque le nombre de permutations de n éléments est n!, l’arbre
de décision d’un tri a donc n! feuilles. On peut montrer facilement, par
récurrence sur h, que le nombre de feuilles nf d’un arbre binaire de hauteur
h, vérifie nf  2h . On en déduit que la hauteur h de l’arbre de décision
vérifie

h log(n!)
or, d’après la formule de Stirling 1
p ⇣ n ⌘n
log(n!) ⇠ log 2⇡n + log = ⇥(nlog n)
e
n
1. sans utiliser la formule de Stirling, on peut remarquer que ( n2 ) 2  n!  nn , ce qui
conduit directement à log(n!) = ⇥(n log n).
48 CHAPITRE 3. ALGORITHMES DE TRI

et donc la hauteur minimale de l’arbre est en ⌦(nlog n).

Comme la hauteur de l’arbre est aussi la longueur de sa plus longue
branche, on en conclut qu’aucun tri par comparaison ne peut avoir une
complexité dans le pire des cas inférieure à O(n ⇥ log n).

3.4 Tri par tas.

Un tas (heap en anglais) est un arbre binaire étiqueté presque complet : tous
ses niveaux sont remplis sauf peut-être le dernier, qui est rempli à partir de
la gauche jusqu’à un certain nœud. Cette disposition entraı̂ne que l’arbre
est forcément presque complètement équilibré (i.e. toutes ses branches ont
la même longueur à un élément près), et les plus longues branches sont
à gauche. La hauteur d’un tas contenant n éléments, i.e. son nombre de
niveaux, est donc blog2 nc + 1 (le nombre de fois que l’on peut diviser n par
2 avant d’obtenir 1).

0
13
hauteur log2 n 1 2
11 7

3 4 5 6
10 3 5 1

7 8 9
4 8 2

Habituellement les tas sont représentés dans des tableaux. Les valeurs du
tas sont stockées dans les premières cases du tableau. Si le tas est composé
de n éléments, ces derniers apparaissent donc aux indices 0, 1,. . . , n 1.
La racine du tas figure dans la case d’indice 0. La disposition des éléments
du tas dans le tableau correspond à un parcours de l’arbre par niveau, en
partant de la racine et de gauche à droite. Le fils gauche du nœud qui figure
à l’indice i, s’il existe, se trouve à l’indice FilsG(i) = 2 ⇥ i + 1, et son fils
3.4. TRI PAR TAS. 49

droit, s’il existe, se trouve à l’indice FilsD(i) = 2 ⇥ i + 2. Inversement, le

père du nœud d’indice i non nul se trouve à l’indice b i 2 1 c.

fils droit
0 1 2 3 4 5 7 8 9 10 11
13 11 7 10 3 5 1 4 8 2 0 5
6 n−1
fils gauche

Si le dernier nœud du tas se trouve à la position n 1, son père se trouve

à la position b n2 1c. C’est le dernier nœud qui a au moins un fils. Les feuilles
de l’arbre se trouvent donc entre la position b n2 c et la position n 1 dans le
tableau puisqu’il n’y a pas de feuilles avant le dernier père.

On définit ensuite une propriété sur les tas : chaque nœud est dans une
relation d’ordre fixée avec ses fils.
Un tas possède la propriété max-heap (resp. min-heap) si tout nœud
porte une valeur supérieure ou égale (resp. inférieure ou égale) à celle de ses
fils : T [pere(i)] T [i] (resp. T [pere(i)]  T [i]). Un tax-max (resp. tas-min)
est un tas qui vérifie la propriété max-heap (resp. min-heap).
Le plus grand élément d’un tas-max T est T [0] ; son plus petit élément
est sur une feuille.
Pour le tri par tas on utilise des tas-max. Les opérations et les techniques
présentées dans ce chapitre s’appliquent de la même façon à des tas basés
sur l’ordre inverse. Les opérations essentielles sur les tas sont :
— la construction du tas,
— l’extraction du maximum,
— l’ajout d’une nouvelle valeur,
— la modification de la valeur d’un nœud.
L’opération Entasser est une opération de base sur les tas. Elle est utilisée
notamment pour la construction des tas ou encore pour l’extraction de la
valeur maximale. Elle consiste à reconstruire le tas lorsque seule la racine
viole (éventuellement) la propriété de supériorité entre un nœud et ses fils,
en faisant descendre dans l’arbre l’élément fautif par des échanges successifs.
50 CHAPITRE 3. ALGORITHMES DE TRI

9 14 14

14 7 9 7 13 7

10 13 5 1 10 13 5 1 10 9 5 1

4 8 2 4 8 2 4 8 2

Fonction Entasser(i,T ,n)

entrée : T est un tas ; le fils gauche et le fils droit du noeud d’indice i
vérifient la propriété Max-heap ; ce n’est pas forcément le
cas du noeud d’indice i.
sortie : La propriété max-heap est vérifiée par le noeud d’indice i.
début
iM ax i
si (FilsG(i) < n) ET (T [FilsG(i)] > T [iM ax]) alors
iM ax := FilsG(i)
si (FilsD(i) < n) ET (T [FilsD(i)] > T [iM ax]) alors
iM ax := FilsD(i)
si (iM ax 6= i) alors
Echanger T [i] et T [iM ax]
Entasser(iM ax,T ,n)

— la condition (FilsG(i) < n) signifie que le fils gauche du nøeud i

existe ;
— si le nœud i est une feuille ou si T [i] est supérieure aux valeurs portées
par ses fils, l’algorithme ne fait rien ;
— si le nœud i a des fils qui portent des valeurs supérieures à T [i], la
fonction échange cette valeur avec la plus grande des valeurs de ses
fils et e↵ectue un appel récursif sur le fils qui porte la valeur T [i].
La fonction Entasser a un coût en O(log2 n) puisque, dans le pire des
cas, il faudra parcourir une branche entièrement.
Extraction de la valeur maximale. La valeur maximale d’un tas qui
vérifie la propriété Max-heap est à la racine de l’arbre. Pour un tas de taille
n stocké dans le tableau T c’est la valeur T [0] si n est non nul. L’extraction
de la valeur maximale consiste à recopier en T [0] la dernière valeur du tas
3.4. TRI PAR TAS. 51

T [n 1], à décrémenter la taille du tas, puis à appliquer l’opération Entasser

à la racine du tas, afin que la nouvelle valeur de la racine prenne sa place.

Fonction ExtraireLeMax(T, n)
entrée : T est un tableau, n est la taille du tas stocké dans T .
sortie : Retourne la valeur maximale et met à jour le tas.
début
max := T [0]
T [0] := T [n 1]
Entasser(0, T, n 1)
retourner hmax, T, n 1i
fin

Exercice 5 Écrivez les algorithmes

1. InsertVal(T, n, v) qui insère une valeur v dans un tasmax T de n
éléments (on suppose que l’on peut accéder à T [n])
2. SupprimeNoeud(T, n, i) qui supprime le nœud i dans le tasmax T
de n éléments.
Dans les deux cas, le tas résultant et un tasmax.

Principe général du tri par tas. Supposons que l’on ait à trier une
suite de n valeurs stockée dans un tableau T . On commence par construire
un tas dans T avec les valeurs de la suite. Ensuite, tant que le tas n’est pas
vide on répète l’extraction de la valeur maximale du tas. Chaque fois, la
valeur extraite est stockée dans le tableau immédiatement après les valeurs
du tas. Lorsque le processus se termine on a donc la suite des valeurs triée
dans le tableau T .

Construction du tas.
Les valeurs de la suite à trier sont stockées dans le tableau T . La procé-
dure consiste à parcourir les noeuds qui ont des fils et à leur appliquer l’opé-
ration Entasser, en commençant par les noeuds qui sont à la plus grande
profondeur dans l’arbre. Il suffit donc de parcourir les noeuds dans l’ordre
décroissant des indices et en partant du dernier noeud qui a des fils, le noeud
d’indice b(n/2)c 1. L’ordre dans lequel les noeuds sont traités garantit que
les sous-arbres sont des tas.
52 CHAPITRE 3. ALGORITHMES DE TRI

Fonction ConstruireUnTas(T, n)
entrée : T est un tableau, n est un entier.
sortie : Structure les n premiers éléments de T sous forme de tas.
début
pour i := bn/2 1c à 0 faire
Entasser(i, T, n)
finpour
retourner T
fin

Invariant : tous les nœuds de T d’indice > i vérifient la propriété max-

heap.
Complexité de la construction. De façon évidente la complexité est au
plus O(n log n). En e↵et la hauteur du tas est log n et on e↵ectue n/2 fois
l’opération Entasser. En fait le coût de la construction est O(n). En e↵et, la
fonction e↵ectue un grand nombre d’entassements sur des arbres de petites
hauteur (pour les noeuds les plus profonds), et très peu d’entassements sur
la hauteur du tas.
Soit h la hauteur du tas construit T . Il a 1 noeud de hauteur h, au
plus 2 noeuds de hauteur h 1, . . . , et au plus 2h 1 noeuds de hauteur 1.
Soit K une constante telle que la complexité de Entasser(i, T, n) soit
 Khi , où hi est la hauteur du sous-arbre de racine i. La complexité C(n)
de l’algorithme ConstruitTas vérifie donc :
h h 1 1
C(n)  K(h + 2(h 1) + 4(h 2) + · · · + 2h 1
)  K2h ( + + · · · + ).
2h 2h 1 2
P1 k
La série k=0 2k converge vers 2. En e↵et,
1
X 1
X 1 1
k k 1+1 1Xk 1 X 1 S
S= = = + = + 1.
2k 2k 2 2k 1 2k 2
k=0 k=1 k=1 k=1

2h
Comme  n, on en déduit que C(n)  2Kn. L’algorithme ConstruitTasMax
est linéaire dans le pire des cas. Cette complexité est atteinte si T est stric-
tement croissant.
Exercice 6 Construisez un tas à partir de T = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

Exercice 7 Si l’on utilise l’algorithme InsertVal pour construire un tas-

max de n éléments, quel est la complexité de l’algorithme ?
3.5. TRI PAR DÉNOMBREMENT, TRI PAR BASE. 53

Tri par tas.

On construit un tas. On utilise le fait que le premier élément du tas est le
plus grand : autant de fois qu’il y a d’éléments, on extrait le premier du tas et
on reconstruit le tas avec les éléments restants. Enlever le premier élément
consiste simplement à l’échanger avec le dernier du tas et à décrémenter
la taille du tas. On rétablit la propriété de tas en appliquant l’opération
Entasser sur ce premier élément.

Fonction TriParTas(T, n)
entrée : T est un tableau de n éléments.
sortie : Trie le tableau T par ordre croissant.
début
ConstruireUnTas(T, n)
pour i := n 1 à 1 faire
Echanger(T, 0, i)
Entasser(0, T, i)
retourner T

La construction du tas coûte O(n). On e↵ectue ensuite n fois un échange et

l’opération Entasser sur un tas de hauteur au plus log n. La complexité du
tri par tas est donc O(n log n).

3.5 Tri par dénombrement, tri par base.

3.5.1 Tri par dénombrement
Le tri par dénombrement (counting sort) est un tri sans comparaisons
qui est stable, c’est-à-dire qu’il respecte l’ordre d’apparition des éléments
dont les clés sont égales. Le tri par dénombrement commence par recenser
les éléments pour chaque valeur possible des clés. Ce comptage préliminaire
permet de connaı̂tre, pour chaque clé c, la position finale du premier élément
de clé c qui apparaı̂t dans la suite à trier. Sur l’exemple ci-dessous on a
recensé dans le tableau T , 3 éléments avec la clé 1, 4 éléments avec la clé 2
et 3 éléments avec la clé 3. On en déduit que le premier élément avec la clé
1 devra être placé à la position 1, le premier élément avec la clé 2 devra être
placé à la position 4, et le premier élément avec la clé 3 devra être placé à
la position 8. Il suffit ensuite de parcourir une deuxième fois les éléments à
trier et de les placer au fur et à mesure dans un tableau annexe (le tableau
R de la figure), en n’oubliant pas, chaque fois qu’un élément de clé c est
54 CHAPITRE 3. ALGORITHMES DE TRI

placé, d’incrémenter la position de l’objet suivant de clé c. De cette façon

les éléments qui ont la même clés apparaissent nécessairement dans l’ordre
de leur apparition dans le tableau initial.

1 2 3 4 5 6 7 8 9 10

T 1 3 1 2 3 2 1 3 2 2

1 2 3
Nombres d’apparitions 3 4 3
1 2 3 4 5 6 7 8 9 10
1 2 3
Indices des premiers à placer 1 4 8 T 1 3 1 2 3 2 1 3 2 2

placement de T[1] en R[1] 2 4 8

placement de T[2] en R[8] R 1 1 1 2 2 2 2 3 3 3

2 4 9
1 2 3 4 5 6 7 8 9 10
placement de T[3] en R[2] 3 4 9

La suite des objets à trier est parcourue deux fois, et la table N b conte-
nant le nombre d’occurrences de chaque clé est parcourue une fois pour
l’initialiser. La complexité finale est donc O(n + k) si les clés des éléments
à trier sont comprises entre 1 et k. Le tri par dénombrement est dit linéaire
(modulo le fait que k doit être comparable à n).

Exercice 8 [CLRS] Décrivez un algorithme de complexité O(n + k) qui

prend en entrée un tableau T comprenant n entiers compris entre 0 et k et
qui pré-traite T de manière à pouvoir répondre à n’importe quelle requête
du type Combien le tableau T a t-il d’éléments dans l’intervalle [a, b] ? en
temps O(1).

3.5.2 Tri par base.

Le tri par dénombrement n’est pas applicable lorsque les valeurs que
peuvent prendre les clés sont très nombreuses. Le principe du tri par base
(radix sort) consiste, dans ce type de cas, à fractionner les clés, et à e↵ectuer
un tri par dénombrement successivement sur chacun des fragments des clés.
3.5. TRI PAR DÉNOMBREMENT, TRI PAR BASE. 55

Fonction TriParDenombrements(T, n, k)
entrée : T est un tableau de n éléments 2 {1, . . . , k}.
sortie : R contient les éléments de T triés par ordre croissant.
début
/* Initialisations */
pour i := 1 à k faire
N b[i] := 0
/* Calcul des nombres d’apparitions */
pour i := 1 à n faire
N b[T [i]] := N b[T [i]] + 1
/* Calcul des indices du premier */
N b[k] := n N b[k] + 1
/* Élément de chaque catégorie */
pour i := k 1 à 1 faire
N b[i] := N b[i + 1] N b[i]
/* Recopie des éléments originaux du tableau T dans R */
pour i := 1 à n faire
R[N b[T [i]]] := T [i]
N b[T [i]] := N b[T [i]] + 1
retourner R

Si on considère les fragments dans le bon ordre (i.e. en commençant par

les fragments de poids le plus faible), après la dernière passe, l’ordre des
éléments respecte l’ordre lexicographique des fragments, et donc la suite est
triée.

Considérons l’exemple suivant dans lequel les clés sont des nombres en-
tiers à au plus trois chi↵res. Le fractionnement consiste simplement à prendre
chacun des chi↵res de l’écriture décimale des clés. La colonne de gauche
contient la suite des valeurs à trier, la colonne suivante contient ces mêmes
valeurs après les avoir triées par rapport au chi↵re des unités, . . . Dans la
dernière colonne les valeurs sont e↵ectivement triées. Du fait que le tri par
dénombrement est stable, si des valeurs ont le même chi↵re des centaines,
alors elles apparaı̂tront dans l’ordre croissant de leurs chi↵res des dizaines,
et si certaines ont le même chi↵re des dizaines alors elles apparaı̂tront dans
l’ordre croissant des chi↵res des unités.
56 CHAPITRE 3. ALGORITHMES DE TRI

536 592 427 167

893 462 536 197
427 893 853 427
167 853 462 462
853 536 167 536
592 427 592 592
197 167 893 853
462 197 197 893

Supposons que l’on ait n valeurs dont les clés sont fractionnées en c
fragments avec k valeurs possibles pour chaque fragment. Le coût du tri par
base est alors O(c⇥n+c⇥k) puisqu’on va e↵ectuer c tris par dénombrement
sur n éléments avec des clés qui auront k valeurs possibles.
Si k = O(n) on peut dire que le tri par base est linéaire. Dans la pratique,
sur des entiers codés sur 4 octets que l’on fragmente en 4, le tri par base est
aussi rapide que le Quick Sort.
Exercice 9 [CLRS] Montrez comment trier n entiers compris entre 0 et
n2 1 en temps O(n).