Algorithmes de tri

Algorithmique 1

Stéphane Grandcolas

Aix-Marseille Université

2023-2024

Contact : [Link]@[Link]

S. Grandcolas, 2024
Tris.

▶ Arbre de décision : tri par insertion

▶ Complexité des tris par comparaison dans le pire des cas :
borne minimale
▶ Tri rapide
▶ Tri par dénombrement, tri par base

S. Grandcolas, 2024
Tris.

organiser un ensemble d’objets selon un ordre déterminé

relation d’ordre : comparaison de clés

dans nos exemple nous confondrons les objets avec leurs clés

▶ tri par comparaison versus tri par indexation

▶ tri sur place : espace mémoire de taille constante
▶ tri stable : préserve l’ordre initial en cas d’égalité

S. Grandcolas, 2024
Quelques tris classiques.
1. Tris en O(n2 ).
▶ tri à bulles,
▶ tri par insertion,
▶ tri par sélection.

2. Tris en O(n × log n).

▶ tri par fusion,
▶ tri par tas,
▶ tri rapide (mais en O(n2 ) dans le pire des cas).

3. Tris spéciaux.
▶ tri shell (probablement O(n1.25 )),
▶ tri par dénombrement (O(n)).

S. Grandcolas, 2024
Tri par insertion

partie triée i partie non triée

Principe : insérer les éléments les uns après les autres dans la
partie triée

S. Grandcolas, 2024
Tri par insertion

partie triée i partie non triée

Principe : insérer les éléments les uns après les autres dans la
partie triée

Insertion : recopie des éléments plus grands vers la droite

S. Grandcolas, 2024
Tri par insertion

procédure TRI_PAR_INSERTION(T [1, . . . , n])

début
pour i := 2 jusqu’à n faire
j := i,
tant que ((j > 1) et (T [j] < T [j − 1])) faire
// la suite T [1, . . . , j − 1] est ordonnée
PERMUTER(T , j, j − 1),
j := j − 1,
fin faire
fin faire
fin procédure

S. Grandcolas, 2024
Tri par insertion

Pire des cas : i − 1 permutations à chaque passage.

n
X
T (n) = (k1 + k2 (i − 1)) = O(n2 )
i=2

Meilleur des cas : aucune permutation (mais une

comparaison).
n
X
T (n) = k = O(n)
i=2

S. Grandcolas, 2024
Nombre d’inversions

Inversion : (i, j) tel que i < j et T [i] > T [j]

7 inversions

3 11 8 12 7 21 19 15

▶ meilleur cas (suite ordonnée) : aucune inversion

▶ pire des cas : (suite triée dans l’ordre décroissant)

n × (n − 1)
inversions
2

S. Grandcolas, 2024
Nombre d’inversions

Permutation de deux éléments consécutifs inversés :

n3
i i +1

n1 a b n2

nb inversions = n1 + n2 + n3 + nbInv (i) + nbInv (i + 1) + 1

S. Grandcolas, 2024
Nombre d’inversions

Permutation de deux éléments consécutifs inversés :

n3
i i +1

n1 b a n2

nb inversions = n1 + n2 + n3 + nbInv (i) + nbInv (i + 1)

S. Grandcolas, 2024
Nombre d’inversions

Permutation de deux éléments consécutifs inversés :

n3
i i +1

n1 b a n2

En permutant deux éléments successifs non ordonnés on diminue de 1 le

nombre d’inversions

Un tri qui n’effectue que ce type d’inversions est en O(n2 )

S. Grandcolas, 2024
Arbre de décision

▶ tris par comparaison

▶ comparaison → décision de permuter ou non

Arbre de décision : représente tous les scénarios possibles

pour une suite de n valeurs

Branche : la suite de permutations faites par le tri pour

produire la séquence ordonnée

S. Grandcolas, 2024
Arbre de décision (tri par insertion)
1 2 3
a b c
a <= b <= > a>b

a b c b a c

b <= c <= > b>c a <= c <= > a>c

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

a <= c <= > a>c b <= c <= > b>c

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

Tri par comparaison ⇒ arbre binaire

S. Grandcolas, 2024
Arbre de décision (tri par insertion)
1 2 3
a b c
a <= b <= > a>b

a b c b a c

b <= c <= > b>c a <= c <= > a>c

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

a <= c <= > a>c b <= c <= > b>c

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

nombre de feuilles = nombre de branches = n!

(1) On peut composer n! suites différentes à partir de n valeurs différentes.
(2) On ne peut pas trier deux suites u et v qui diffèrent par le rang de certains éléments avec la même
séquence de permutations ρ : si ∃i, j tels que ui < uj et vi > vj , alors ρ(i) < ρ(j) et ρ(i) > ρ(j).

S. Grandcolas, 2024
Complexité des tris par comparaison

Nombre de feuilles : n!

hauteur de l’arbre de décision :

h(n) ≥ log(n!)

S. Grandcolas, 2024
Complexité des tris par comparaison

Nombre de feuilles : n!

hauteur de l’arbre de décision :

h(n) ≥ log(n!)
√ n n


or n! ∽ 2πn × e
(formule de Stirling)

donc
n
n
h(n) ≥ log = n × (log n − log e) ≈ n × log n
e

S. Grandcolas, 2024
Tri rapide (quick sort)
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 Choisir pivot dans T [g , . . . , d],
3 m :=PARTITIONNER(T , g , d, pivot),
4 TRI_RAPIDE (T , g , m − 1),
5 TRI_RAPIDE (T , m + 1, d),

▶ tri par comparaisons en place

▶ tableau indexé
▶ le plus rapide dans le cas général
▶ très utilisé

S. Grandcolas, 2024
Tri rapide (quick sort)
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 Choisir pivot dans T [g , . . . , d],
3 m :=PARTITIONNER(T , g , d, pivot),
4 TRI_RAPIDE (T , g , m − 1), { m − 1 < d}
5 TRI_RAPIDE (T , m + 1, d), { m + 1 > g}

S. Grandcolas, 2024
Tri rapide (quick sort)
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 Choisir pivot dans T [g , . . . , d],
3 m :=PARTITIONNER(T , g , d, pivot),
4 TRI_RAPIDE (T , g , m − 1), { m − 1 < d}
5 TRI_RAPIDE (T , m + 1, d), { m + 1 > g}

Partition : g pivot d
17 23 4 8 13 11 2 9 7 14 6

g m d
9 8 6 4 2 7 11 13 23 17 14

≤ pivot ≥ pivot

S. Grandcolas, 2024
Tri rapide (quick sort)
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 Choisir pivot dans T [g , . . . , d],
3 m :=PARTITIONNER(T , g , d, pivot),
4 TRI_RAPIDE (T , g , m − 1),
5 TRI_RAPIDE (T , m + 1, d),

17 23 4 8 13 11 2 9 7 14 6

9 8 6 4 2 7 13 23 17 14

4 2 7 9 8 17 14 13

2 7 8 13 17

S. Grandcolas, 2024
Tri rapide (quick sort)
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 Choisir pivot dans T [g , . . . , d],
3 m :=PARTITIONNER(T , g , d, pivot), O(n)
4 TRI_RAPIDE (T , g , m − 1), T (n/2)
5 TRI_RAPIDE (T , m + 1, d), T (n/2)

Dans le meilleur cas

T (n) = 1 + n + 2 × T (n/2) = O(n × log n)

S. Grandcolas, 2024
Tri rapide (quick sort)
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 Choisir pivot dans T [g , . . . , d],
3 m :=PARTITIONNER(T , g , d, pivot), O(n)
4 TRI_RAPIDE (T , g , m − 1), T (0)
5 TRI_RAPIDE (T , m + 1, d), T (n − 1)

Dans le pire des cas

T (n) = 1 + n + T (n − 1) = O(n2 )

S. Grandcolas, 2024
Partition type drapeau

Après la partition :
g d
< pivot = pivot > pivot

S. Grandcolas, 2024
Partition type drapeau

Pendant la partition :
g i d
< pivot = pivot x > pivot

éléments en attente

S. Grandcolas, 2024
Partition type drapeau

cas 1 : x > pivot : permutation avec le dernier en attente

g i d
< pivot = pivot x > pivot

g i d
< pivot = pivot x > pivot

S. Grandcolas, 2024
Partition type drapeau

cas 2 : x = pivot : extension de la zone

g i d
< pivot = pivot x > pivot

g i d
< pivot = pivot x > pivot

S. Grandcolas, 2024
Partition type drapeau

cas 3 : x < pivot : permutation avec le premier égal au pivot

g i d
< pivot = pivot x > pivot

g i d
< pivot x = pivot > pivot

S. Grandcolas, 2024
Partition rapide

g pivot d

10 7 11 23 4 8 13 11 2 9 12 6 18 17 14

Recherche d’un élément plus grand que le pivot à gauche,

et d’un élément plus petit à droite

S. Grandcolas, 2024
Partition rapide

g i pivot j d

10 7 11 23 4 8 13 11 2 9 12 6 18 17 14

≥ pivot ≤ pivot

à gauche : stoppe avec xi ≥ pivot

à droite : stoppe avec xj ≤ pivot

⇒ permutation de xi et xj

S. Grandcolas, 2024
Partition rapide

g i pivot j d

10 7 6 23 4 8 13 11 2 9 12 11 18 17 14

à gauche : stoppe avec xi ≥ pivot

à droite : stoppe avec xj ≤ pivot

⇒ permutation de xi et xj

S. Grandcolas, 2024
Partition rapide

g pivot d

10 7 6 23 4 8 13 11 2 9 12 11 18 17 14

Extension des zones

S. Grandcolas, 2024
Partition rapide

g pivot d

10 7 6 23 4 8 13 11 2 9 12 11 18 17 14

Recherche d’un plus grand à gauche et d’un plus petit à droite

S. Grandcolas, 2024
Partition rapide

g pivot d

10 7 6 9 4 8 13 11 2 23 12 11 18 17 14

Permutation et extension des zones

S. Grandcolas, 2024
Partition rapide

g pivot d

10 7 6 9 4 8 13 11 2 23 12 11 18 17 14

Recherche d’un plus grand à gauche et d’un plus petit à droite

S. Grandcolas, 2024
Partition rapide

g pivot d

10 7 6 9 4 8 2 11 13 23 12 11 18 17 14

Permutation et extension des zones

S. Grandcolas, 2024
Partition rapide

g pivot d

10 7 6 9 4 8 2 11 13 23 12 11 18 17 14

Dernière permutation

S. Grandcolas, 2024
Partition rapide

g d

10 7 6 9 4 8 2 11 13 23 12 11 18 17 14

Produit deux zones strictement plus petites que [g ..d]

La partition est en O(n)

S. Grandcolas, 2024
Quick sort avec partition rapide
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 a := g , b := d,
3 pivot := T [(a + b)/2],
4 tant que (a ≤ b) faire
5 tant que (T [a] < pivot) faire
6 a := a + 1,
7 tant que (T [b] > pivot) faire
8 b := b − 1,
9 si (a ≤ b) alors
10 PERMUTER(T , a, b),
11 a := a + 1,
12 b := b − 1,
13 TRI_RAPIDE (T , g , b),
14 TRI_RAPIDE (T , a, d),
15 fin fonction

S. Grandcolas, 2024
Quick sort : terminaison
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors n =d −g +1>1
2 a := g , b := d,
3 pivot := T [(a + b)/2],
4 tant que (a ≤ b) faire
5 tant que (T [a] < pivot) faire la première fois stoppée par le pivot,
6 a := a + 1, ensuite stoppée par T [b]
7 tant que (T [b] > pivot) faire
8 b := b − 1,
9 si (a ≤ b) alors
10 PERMUTER(T , a, b),
11 a := a + 1,
12 b := b − 1,
13 TRI_RAPIDE (T , g , b),
14 TRI_RAPIDE (T , a, d),
15 fin fonction

S. Grandcolas, 2024
Quick sort : terminaison
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors n =d −g +1>1
2 a := g , b := d,
3 pivot := T [(a + b)/2],
4 tant que (a ≤ b) faire
5 tant que (T [a] < pivot) faire
6 a := a + 1,
7 tant que (T [b] > pivot) faire la première fois stoppée par le pivot,
8 b := b − 1, ensuite stoppée par T [a − 1]
9 si (a ≤ b) alors
10 PERMUTER(T , a, b),
11 a := a + 1,
12 b := b − 1,
13 TRI_RAPIDE (T , g , b),
14 TRI_RAPIDE (T , a, d),
15 fin fonction

S. Grandcolas, 2024
Quick sort : terminaison
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors n =d −g +1>1
2 a := g , b := d,
3 pivot := T [(a + b)/2],
4 tant que (a ≤ b) faire
5 tant que (T [a] < pivot) faire
6 a := a + 1,
7 tant que (T [b] > pivot) faire
8 b := b − 1,
9 si (a ≤ b) alors forcément vrai la première fois
10 PERMUTER(T , a, b),
11 a := a + 1,
12 b := b − 1,
13 TRI_RAPIDE (T , g , b),
14 TRI_RAPIDE (T , a, d),
15 fin fonction

S. Grandcolas, 2024
Quick sort : terminaison
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors n =d −g +1>1
2 a := g , b := d,
3 pivot := T [(a + b)/2],
4 tant que (a ≤ b) faire
5 tant que (T [a] < pivot) faire
6 a := a + 1,
7 tant que (T [b] > pivot) faire
8 b := b − 1,
9 si (a ≤ b) alors forcément vrai la première fois
10 PERMUTER(T , a, b),
11 a := a + 1, on incrémente a au moins une fois
12 b := b − 1, on décrémente b au moins une fois
13 TRI_RAPIDE (T , g , b),
14 TRI_RAPIDE (T , a, d),
15 fin fonction

S. Grandcolas, 2024
Quick sort : terminaison
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors n =d −g +1>1
2 a := g , b := d,
3 pivot := T [(a + b)/2],
4 tant que (a ≤ b) faire
5 tant que (T [a] < pivot) faire
6 a := a + 1,
7 tant que (T [b] > pivot) faire
8 b := b − 1,
9 si (a ≤ b) alors forcément vrai la première fois
10 PERMUTER(T , a, b),
11 a := a + 1, on incrémente a au moins une fois
12 b := b − 1, on décrémente b au moins une fois
13 TRI_RAPIDE (T , g , b), ici b < d donc b − g + 1 < n
14 TRI_RAPIDE (T , a, d), ici a > g donc d − a + 1 < n
15 fin fonction

S. Grandcolas, 2024
Quick sort : justesse
fonction TRI_RAPIDE (T , g , d)
1 si (g < d) alors
2 a := g , b := d,
3 pivot := T [(a + b)/2],
4 tant que (a ≤ b) faire
{∀i, si g ≤ i < a alors T [i] ≤ v , et si b < i ≤ d alors T [i] ≥ v ,}
5 tant que (T [a] < pivot) faire
6 a := a + 1, {T [a − 1] < v }
7 tant que (T [b] > pivot) faire
8 b := b − 1, {T [b + 1] > v }
9 si (a ≤ b) alors
10 PERMUTER(T , a, b),
{T [a] ≤ v et T [b] ≥ v }
11 a := a + 1,
12 b := b − 1,
{donc si i < a alors T [i] ≤ v et si i > b alors T [i] ≥ v ,}
13 TRI_RAPIDE (T , g , b), {b < a et ∀i, i < a on a T [i] ≤ v }
14 TRI_RAPIDE (T , a, d), {a > b et ∀i, i > b on a T [i] ≥ v }
15 fin fonction

S. Grandcolas, 2024
Tri par dénombrement.
2 2 1 2 1 3 3 1 2 3 1 1

1 1
1 22 3
1 1 3
2 2 3

Tri sans comparaison : suppose que l’on sait indexer les

éléments à trier, i.e. affecter à chacun un rang
▶ qui dépend uniquement de sa valeur
▶ qui correspond à l’ordre défini sur les éléments

tri du facteur qui prépare sa tournée

tri de valeurs entières assez proches et nombreuses

S. Grandcolas, 2024
Tri par dénombrement.
Calcul des nombres d’apparitions

0 1 2 3 4 5 6 7 8 9

T 0 2 0 1 2 1 0 2 1 1

0 1 2
Nombres d’apparitions nb 3 4 3

S. Grandcolas, 2024
Tri par dénombrement.
Calcul des positions des premiers de chaque classe

0 1 2 3 4 5 6 7 8 9

T 0 2 0 1 2 1 0 2 1 1

0 1 2
Nombres d’apparitions nb 3 4 3

0 1 2
Indices des premiers pos 0 3 7

S. Grandcolas, 2024
Tri par dénombrement.
Positionnement dans le tableau résultat

0 1 2 3 4 5 6 7 8 9

T 0 2 0 1 2 1 0 2 1 1

0 1 2
Nombres d’apparitions nb 3 4 3
0 1 2 3 4 5 6 7 8 9
0 1 2
Indices des premiers pos 0 3 7
T 0 2 0 1 2 1 0 2 1 1

R − − − − − − − − − −
0 1 2 3 4 5 6 7 8 9

S. Grandcolas, 2024
Tri par dénombrement.
Positionnement dans le tableau résultat

0 1 2 3 4 5 6 7 8 9

T 0 2 0 1 2 1 0 2 1 1

0 1 2
Nombres d’apparitions nb 3 4 3
0 1 2 3 4 5 6 7 8 9
0 1 2
Indices des premiers pos 0 3 7
T 0 2 0 1 2 1 0 2 1 1

placement de T[0] en R[0] pos 1 3 7

R 0 − − − − − − − − −
0 1 2 3 4 5 6 7 8 9

S. Grandcolas, 2024
Tri par dénombrement.
Positionnement dans le tableau résultat

0 1 2 3 4 5 6 7 8 9

T 0 2 0 1 2 1 0 2 1 1

0 1 2
Nombres d’apparitions nb 3 4 3
0 1 2 3 4 5 6 7 8 9
0 1 2
Indices des premiers pos 0 3 7
T 0 2 0 1 2 1 0 2 1 1

placement de T[0] en R[0] pos 1 3 7

placement de T[1] en R[7]

R 0 − − − − − − 2 − −
pos 1 3 8
0 1 2 3 4 5 6 7 8 9

S. Grandcolas, 2024
Tri par dénombrement.
Positionnement dans le tableau résultat

0 1 2 3 4 5 6 7 8 9

T 0 2 0 1 2 1 0 2 1 1

0 1 2
Nombres d’apparitions nb 3 4 3
0 1 2 3 4 5 6 7 8 9
0 1 2
Indices des premiers pos 0 3 7
T 0 2 0 1 2 1 0 2 1 1

placement de T[0] en R[0] pos 1 3 7

placement de T[1] en R[7]

R 0 0 − − − − − 2 − −
pos 1 3 8
0 1 2 3 4 5 6 7 8 9

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

S. Grandcolas, 2024
Tri par dénombrement.
fonction TRI_PAR_DENOMBREMENTS(T , n)
{In : T un tableau de n éléments}
{Out : R le tableau trié des éléments de T }
début
pour i := 0 à k − 1 faire initialisations
nb[i] := 0,
pour i := 1 à n faire calcul des nombres d’apparitions
nb[T [i]] := nb[T [i]] + 1,
pos[0] := 0, calcul des indices du premier
pour i := 1 à k − 1 faire élément de chaque catégorie
pos[i] := pos[i − 1] + nb[i − 1],
pour i := 1 à n faire recopie des élément originaux
R[pos[T [i]]] := T [i], du tableau T dans R
pos[T [i]] := pos[T [i]] + 1,
renvoyer R
fin procédure

Complexité : O(n + k).

S. Grandcolas, 2024
Tri par base.
Utilise le tri par dénombrement en plusieurs passes

536
893
427
167
853
592
197
462

S. Grandcolas, 2024
Tri par base.
Utilise le tri par dénombrement en plusieurs passes

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

S. Grandcolas, 2024
Tri par base.
Utilise le tri par dénombrement en plusieurs passes

536 592 427

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

S. Grandcolas, 2024
Tri par base.
Utilise le tri par dénombrement en plusieurs passes

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

n nombres à c chiffres en base k : O(c × n + c × k).

Si k = O(n) le tri par base est linéaire (O(n)).

S. Grandcolas, 2024