Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Tris
Thomas Bellitto, Alix Munier-Kordon et Maryse Pelletier
LIP6
Sorbonne Université
Paris
Module LU2IN003 Algorithmique Elémentaire
1
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Plan du cours
1 Choisir un algorithme sur les tris
2 Insertion et autres tris simples
3 Quicksort sur les listes
4 Tri fusion de listes
5 Conclusion
2
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Tris de comparaison et stabilité
Definition
Un algorithme de tri est dit de comparaison si il compare les
éléments deux à deux pour les trier.
Definition
Un algorithme de tri est dit stable si il n’inverse pas l’ordre de
deux éléments de même clef.
Definition
Un algorithme de tri est dit en place si il ne nécessite pas de
dupliquer une partie des éléments à trier.
3
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Autres caractéristiques
Complexité pire-cas, meilleur cas, moyenne.
Difficulté algorithmique.
le tri par insertion, le tri par sélection et le tri à bulles sont
dits simples car faciles à comprendre et à programmer.
Structure linéaire utilisée : tableau, listes simplement ou
doublement chaînées, fichiers.
Certains tris s’adaptent facilement pour trier des listes
chaînées.
4
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Complexité minimale d’un tri de comparaison
Theorem
Tout algorithme de tri de comparaison est de complexité d’au
minimum O(n log n) dans le pire des cas.
Impossible d’espérer un tri de comparaison de complexité
inférieure à O(n log n) !
5
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Principe du tri par insertion
Soit n le nombre d’éléments du tableau à trier.
1 Au début de l’étape j ∈ {1, · · · , n − 1}, tab[0 · · · j − 1] est
trié;
2 on insère alors tab[j] à sa place dans tab[0 · · · j − 1];
3 tab[0 · · · j] est alors un tableau trié.
6
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Algorithme de tri par insertion
def insertionSort(tab):
j = 1
n = len(tab)
while j != n:
# inserer tab[j] dans tab[0...j-1]
# a sa place
insertionElem(tab, j)
j = j + 1
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Principe de insertionElem
En entrée, j ∈ {1 · · · , n − 1} et tab[0 · · · j − 1] est un tableau
trié. insertionElem insère la valeur tab[j] à sa place dans
tab[0 · · · j − 1].
1 On sauvegarde tmp = tab[j];
2 on parcourt le tableau tab[0 · · · j − 1] en décalant chaque
élément d’une case vers la droite;
3 on s’arrête dès que l’on a trouvé la place de tmp.
8
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Fonction insertionElem
def insertionElem(tab, j):
tmp = tab[j]
i = j-1
while i > -1 and tab[i] > tmp:
tab[i+1] = tab[i]
i = i - 1
tab[i+1] = tmp
9
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Exécution de insertionElem(tab, 4)
j =4 tmp = tab[j] = 5 i =j −1=3
i =3 1 3 6 7 5 7>5
i =2 1 3 6 7 7 6>5
i =1 1 3 6 6 7 3≤5
1 3 5 6 7 tab[i + 1] = tmp
10
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Complexité et stabilité du tri par insertion
Le tri par insertion est stable ;
Dans le meilleur des cas, le tableau est déja trié :
Complexité de Ω(n) ;
Dans le pire des cas, le tableau est en ordre décroissant :
Complexité de O(n2 ).
11
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Complexité et stabilité des tris simples pour des
tableaux
Tri Complexité Stable
Insertion Ω(n)/O(n2 ) Oui −
Bulles Θ(n2 ) Oui Voir TD 2/5
Sélection Θ(n2 ) Non Voir TD 2/4
Que peut-on dire dans le cas de listes simplement ou
doublement chaînées ?
12
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Principe du Quicksort sur les listes
Soient L une liste non vide et x1 = L[0]. x1 est appelé le “Pivot” ;
1 Eclater les éléments de L \ {x1 } en deux sous-listes L1 et
L2 telles que :
∀y ∈ L1, y < x1 et ∀y ∈ L2, y ≥ x1 .
2 Si L est vide, retourner vide. Sinon, retourner la liste
L0 = Quicksort(L1).(x1 ).Quicksort(L2).
La notation `.`0 désigne la liste constituée de la concaténation
des listes ` et `0 .
13
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Quicksort
def Quicksort(L):
if (len(L)>1):
L1=[] ; L2=[] ; L3=[]
[Link](L[0])
Eclatement(L, L1, L2)
return Quicksort(L1)+L3+Quicksort(L2)
return L
14
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Fonction d’éclatement du Quicksort
def Eclatement(L, L1, L2):
x=L[0]
for y in L[1:]:
if (y<x):
[Link](y)
else:
[Link](y)
15
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Arbre des exécutions de
Quicksort([12,2,17,25,7,5])
QS([12,2,17,25,7,5])
QS([2,7,5]) QS([17,25])
QS([]) QS([7,5]) QS([]) QS([25])
QS([5]) QS([])
16
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Complexité et stabilité du Quicksort pour une liste
circulaire doublement chaînée
1 La complexité de l’éclatement est en Θ(n) ;
2 Si la liste est déjà triée, la complexité est en O(n2 ) ;
3 Dans le meilleur des cas, si la liste est divisée en deux à
chaque appel, la complexité est en Ω(n log n) ;
4 On peut démontrer (mais pas dans ce cours), que la
complexité en moyenne du Quicksort est en n log n.
5 Est-ce-que le Quicksort est stable ?
17
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Les monotonies
Soit L = (1, 5, 8, 3, 7, 2, 12, 4, 9, 15) une liste d’entiers à trier en
ordre croissant.
Definition
Une monotonie de L est une sous-liste maximale d’éléments
consécutifs en ordre croissant.
Les monotonies de L sont les sous-listes (1, 5, 8), (3, 7), (2, 12)
et (4, 9, 15).
18
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Opération de fusion de deux listes
Consiste à construire une seule liste à partir de deux listes L1
et L2 en prenant en premier de manière récursive, l’élément
min(L1[0], L2[0]).
La fusion de L1 = (1, 5, 8, 2, 12) avec L2 = (3, 7, 4, 9, 15)
renvoie
L = (1, 3, 5, 7, 4, 8, 2, 9, 12, 15)
19
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
def fusion(L1,L2):
if (L1 == []):
return L2
if (L2 == []):
return L1
if (L1[0]<= L2[0]):
R=fusion(L1[1: ], L2)
[Link](0, L1[0])
return R
R=fusion(L1, L2[1: ])
[Link](0, L2[0])
return R
20
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Evolution du nombre de monotonies
Theorem
Soit L la liste obtenue par fusion des sous-listes L1 et L2 non
vides. Si m1 , m2 et m représentent le nombre de monotonies
des listes L1, L2 et L, alors m < m1 + m2 .
Pour L1 = (1, 5, 8, 2, 12), m1 = 2.
Pour L2 = (3, 7, 4, 9, 15), m2 = 2.
La fusion donne la liste L = (1, 3, 5, 7, 4, 8, 2, 9, 12, 15) avec
m = 3.
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Principe du tri fusion itératif
1 Eclatements/fusions en deux sous-listes selon les
monotonies jusqu’à obtenir une liste triée.
2 La fonction d’éclatement de L en deux sous-listes L1 et L2
ne doit pas augmenter le nombre global de monotonies : la
première monotonie de L est placée dans L1, la seconde
dans L2, la troisième dans L1...etc...
Par exemple, l’éclatement de L = (1, 5, 8, 3, 7, 2, 12, 4, 9, 15)
permet d’obtenir les deux sous-listes L1 = (1, 5, 8, 2, 12) et
L2 = (3, 7, 4, 9, 15).
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
def eclatement ( L, L1, L2) :
listeL1 = True
pred = L[0]
[Link](pred)
i = 1
while (i<len(L)):
if (pred > L[i]):
listeL1=not listeL1
if listeL1:
[Link](L[i])
else:
[Link](L[i])
pred=L[i]
i = i+1
23
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
»> triFusionMonotonies(L)
L = [1, 5, 8, 3, 7, 2, 12, 4, 9, 15]
L1 = [1, 5, 8, 2, 12]
L2 = [3, 7, 4, 9, 15]
L = [1, 3, 5, 7, 4, 8, 2, 9, 12, 15]
L1 = [1, 3, 5, 7, 2, 9, 12, 15]
L2 = [4, 8]
L = [1, 3, 4, 5, 7, 2, 8, 9, 12, 15]
L1 = [1, 3, 4, 5, 7]
L2 = [2, 8, 9, 12, 15]
L = [1, 2, 3, 4, 5, 7, 8, 9, 12, 15]
L1 = [1, 2, 3, 4, 5, 7, 8, 9, 12, 15]
L2 = []
L = [1, 2, 3, 4, 5, 7, 8, 9, 12, 15]
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
def triFusionMonotonies(L):
if len(L)>1:
L1 = []
L2 = []
eclatement(L,L1,L2)
while (len(L2)>0):
L=fusion(L1,L2)
L1 = []
L2 = []
eclatement(L, L1, L2)
return L1
return L
25
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Convergence et complexité du tri fusion itératif pour
une liste circulaire doublement chaînée
1 Le nombre de monotonies de L décroît strictement en
fonction du nombre d’it́érations et L possède au plus
n = |L| monotonies. Donc, l’algorithme converge en au
plus n itérations.
2 La fusion est en O(n) et l’éclatement est en Θ(n). Donc, le
tri fusion est en O(n2 ).
3 Est-ce que le tri par fusion de monotonies est stable ?
4 Peut-on utiliser le tri par fusion de monotonies pour trier un
fichier ?
26
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Complexité et stabilité des tris
Tri Tableau Liste doubl. chaînée circulaire Stable
Insertion Ω(n)/O(n2 ) Ω(n)/O(n2 ) Oui
Sélection (tableaux) Θ(n2 ) × × × × ×× Non
Sélection (listes) × × × × ×× Θ(n2 ) Oui
Bulle Θ(n2 ) Θ(n2 ) Oui
Quicksort (tableaux) Ω(n log n)/O(n2 ) × × × × ×× Non
Quicksort (listes) × × × × ×× Ω(n log n)/O(n2 ) Oui
Fusion Θ(n log n) Θ(n log n) Oui
Fusion de monotonies × × × × ×× Ω(n)/O(n2 ) Non
27
Choisir un algorithme sur les tris
Insertion et autres tris simples
Quicksort sur les listes
Tri fusion de listes
Conclusion
Conclusion
1 De nombreuses façons de trier une structure linéaire. Il
faut choisir en fonction de la structure et des valeurs à trier,
mais aussi de la complexité recherchée.
2 Deux tris classiques restent à voir : Radix (TD 5) et Tri par
Tas (cours/TD sur les arbres).
28