Les Algorithmes de Tri
Les Algorithmes de Tri
Les Algorithmes de Tri
Email: lelia.blin@lip6.fr
Transparents : http://www-npa.lip6.fr/~blin/Enseignements.html
But :
Ré-ordonner les valeurs de la façon suivante
T [i] ≤ T [i + 1]∀i ∈ [1..T aillemax]
Tris avancés
Tri Fusion
Tri rapide
Principe :
A tout moment, le tableau à trier sera en 2 parties :
1. Une partie triée [1..T ] : T est la taille courante
2. Une partie non triée [T + 1..TM ax]
. . . . . . ....... . . ..... .
0 1 2 3 4 5 T T+1 Tmax
Algorithme et exemple
Algorithme Exemple
7 7 3 1 9 2 5
4 7 3 1 9 2 5
4 4 7 1 9 2 5
3 4 7 1 9 2 5
Algorithme et exemple
Algorithme Exemple
3 3 4 7 9 2 5
1 3 4 7 9 2 5
Algorithme et exemple
Algorithme Exemple
Algorithme et exemple
Algorithme cle: 2 , j: 4
def tri_insertion(L): 1 3 4 7 9 2 5
n =len(L)
for i in range(1,n):
cle = L[i]
j = i-1 1 3 4 7 9 9 5
while j>=0 and L[j] > cle:
L[j+1] = L[j]
j = j-1
1 3 4 7 7 9 5
L[j+1] = cle
return(L)
1 3 4 4 7 9 5
1 3 3 4 7 9 5
1 2 3 4 7 9 5
Algorithme et exemple
Algorithme cle: 5 , j: 5
def tri_insertion(L): 1 2 3 4 7 9 5
n =len(L)
for i in range(1,n):
cle = L[i]
j = i-1 1 2 3 4 7 9 9
while j>=0 and L[j] > cle:
L[j+1] = L[j]
j = j-1
1 2 3 4 7 7 9
L[j+1] = cle
return(L)
1 2 3 4 5 7 9
Preuve de l'algorithme
Boucle principale: constat
Au début de chaque itération de la boucle for
le sous-tableau L[1..j − 1] se compose des éléments qui occupaient
initialement les positions L[1..j − 1].
Invariant de boucle
Nous devons montrer trois choses, concernant l'invariant de boucle :
1. Initialisation :
Il est vrai avant la première itération de la boucle.
2. Conservation :
S’il est vrai avant une itération de la boucle,
il le reste avant l’itération suivante.
3. Terminaison :
Une fois terminée la boucle, l’invariant fournit une propriété utile qui aide
à montrer la validité de l’algorithme.
Invariant de boucle
Nous devons montrer trois choses, concernant l'invariant de boucle :
1. Initialisation :
Il est vrai avant la première itération de la boucle.
2. Conservation :
S’il est vrai avant une itération de la boucle,
il le reste avant l’itération suivante.
3. Terminaison :
Une fois terminée la boucle, l’invariant fournit une propriété utile qui aide
à montrer la validité de l’algorithme.
Si les deux premières propriétés sont véri[ées, alors l’invariant est vrai avant
chaque itération de la boucle.
La troisième propriété est utilisé pour prouver la validité de l’algorithme.
Complexité temporelle
Algorithme
def tri_insertion(L):
1:n =len(L)
2:for i in range(1,n):
3: cle = L[i]
4: j = i-1
5: while j>=0 and L[j] > cle:
6: L[j+1] = L[j]
7: j = j-1
8: L[j+1] = cle
9: return(L)
cout
A chaque étape,
Choisir le plus petit élément de la partie non triée
Algorithme et exemple
7 4 3 1 9 2 5
Algorithme
def tri_selection(tab):
for i in range(len(tab)): --- i: 0
min = i j: 1 min: 0 tab[ 0 ]= 7 - tab[ 1 ]= 4
for j in range(i+1, len(tab)): min change min= 1
if tab[min] > tab[j]: j: 2 min: 1 tab[ 1 ]= 4 - tab[ 2 ]= 3
min = j min change min= 2
tmp = tab[i] j: 3 min: 2 tab[ 2 ]= 3 - tab[ 3 ]= 1
tab[i] = tab[min] min change min= 3
tab[min] = tmp j: 4 min: 3 tab[ 3 ]= 1 - tab[ 4 ]= 9
return tab j: 5 min: 3 tab[ 3 ]= 1 - tab[ 5 ]= 2
j: 6 min: 3 tab[ 3 ]= 1 - tab[ 6 ]= 5
7 4 3 1 9 2 5
1 4 3 7 9 2 5
Algorithme et exemple
1 4 3 7 9 2 5
Algorithme
def tri_selection(tab):
for i in range(len(tab)): --- i: 1
min = i j: 2 min: 1 tab[ 1 ]= 4 - tab[ 2 ]= 3
for j in range(i+1, len(tab)): min change min= 2
if tab[min] > tab[j]: j: 3 min: 2 tab[ 2 ]= 3 - tab[ 3 ]= 7
min = j j: 4 min: 2 tab[ 2 ]= 3 - tab[ 4 ]= 9
tmp = tab[i] j: 5 min: 2 tab[ 2 ]= 3 - tab[ 5 ]= 2
tab[i] = tab[min] min change min= 5
tab[min] = tmp j: 6 min: 5 tab[ 5 ]= 2 - tab[ 6 ]= 5
return tab
1 4 3 7 9 2 5
1 2 3 7 9 4 5
Algorithme et exemple
1 2 3 7 9 4 5
Algorithme
def tri_selection(tab):
for i in range(len(tab)): --- i: 2
min = i j: 3 min: 2 tab[ 2 ]= 3 - tab[ 3 ]= 7
for j in range(i+1, len(tab)): j: 4 min: 2 tab[ 2 ]= 3 - tab[ 4 ]= 9
if tab[min] > tab[j]: j: 5 min: 2 tab[ 2 ]= 3 - tab[ 5 ]= 4
min = j j: 6 min: 2 tab[ 2 ]= 3 - tab[ 6 ]= 5
tmp = tab[i]
tab[i] = tab[min]
tab[min] = tmp 1 2 3 7 9 4 5
return tab
1 2 3 7 9 4 5
Algorithme et exemple
1 2 3 7 9 4 5
Algorithme
def tri_selection(tab):
for i in range(len(tab)): --- i: 3
min = i j: 4 min: 3 tab[ 3 ]= 7 - tab[ 4 ]= 9
for j in range(i+1, len(tab)): j: 5 min: 3 tab[ 3 ]= 7 - tab[ 5 ]= 4
if tab[min] > tab[j]: min change min= 5
min = j j: 6 min: 5 tab[ 5 ]= 4 - tab[ 6 ]= 5
tmp = tab[i]
tab[i] = tab[min]
tab[min] = tmp 1 2 3 7 9 4 5
return tab
1 2 3 4 9 7 5
Algorithme et exemple
1 2 3 4 9 7 5
Algorithme
def tri_selection(tab):
for i in range(len(tab)): --- i: 4
min = i j: 5 min: 4 tab[ 4 ]= 9 - tab[ 5 ]= 7
for j in range(i+1, len(tab)): min change min= 5
if tab[min] > tab[j]: j: 6 min: 5 tab[ 5 ]= 7 - tab[ 6 ]= 5
min = j min change min= 6
tmp = tab[i]
tab[i] = tab[min]
tab[min] = tmp 1 2 3 4 9 7 5
return tab
1 2 3 4 5 7 9
Algorithme et exemple
Algorithme
def tri_selection(tab): 1 2 3 4 5 7 9
for i in range(len(tab)):
min = i
for j in range(i+1, len(tab)):
if tab[min] > tab[j]: --- i: 5
min = j j: 6 min: 5 tab[ 5 ]= 7 - tab[ 6 ]= 9
tmp = tab[i]
tab[i] = tab[min]
tab[min] = tmp
1 2 3 4 5 7 9
return tab
1 2 3 4 5 7 9
Algorithme et exemple
Algorithme
def tri_selection(tab): 1 2 3 4 5 7 9
for i in range(len(tab)):
min = i
for j in range(i+1, len(tab)):
if tab[min] > tab[j]: --- i: 6
min = j
tmp = tab[i]
tab[i] = tab[min]
1 2 3 4 5 7 9
tab[min] = tmp
return tab
1 2 3 4 5 7 9
A chaque itération :
Recherche du minimum : n − T ( T taille courante)
Complexité : O(n2 )
sont inférieurs
Algorithme et exemple
7 4 3 1 9 2 5
Algorithme
def tri_bulle(tab): 4 7 3 1 9 2 5
n = len(tab)
for i in range(0,n):
for j in range(n-i-1):
if tab[j] > tab[j+1] : 4 3 7 1 9 2 5
tmp=tab[j+1]
tab[j+1]=tab[j]
tab[j] = tmp
return(tab) 4 3 1 7 9 2 5
---i: 0
j: 0 tab[ 0 ]= 7 - tab[ 1 ]= 4 <-> 4 3 1 7 9 2 5
j: 1 tab[ 1 ]= 7 - tab[ 2 ]= 3 <->
j: 2 tab[ 2 ]= 7 - tab[ 3 ]= 1 <->
j: 3 tab[ 3 ]= 7 - tab[ 4 ]= 9 4 3 1 7 2 9 5
j: 4 tab[ 4 ]= 9 - tab[ 5 ]= 2 <->
j: 5 tab[ 5 ]= 9 - tab[ 6 ]= 5 <->
Algorithme et exemple
4 3 1 7 2 5 9
Algorithme
def tri_bulle(tab): 4 3 1 7 2 5 9
n = len(tab)
for i in range(0,n):
for j in range(n-i-1):
if tab[j] > tab[j+1] : 3 4 1 7 2 5 9
tmp=tab[j+1]
tab[j+1]=tab[j]
tab[j] = tmp
return(tab) 3 1 4 7 2 5 9
---i: 1
j: 0 tab[ 0 ]= 4 - tab[ 1 ]= 3 <-> 3 1 4 7 2 5 9
j: 1 tab[ 1 ]= 4 - tab[ 2 ]= 1 <->
j: 2 tab[ 2 ]= 4 - tab[ 3 ]= 7
j: 3 tab[ 3 ]= 7 - tab[ 4 ]= 2 <-> 3 1 4 2 7 5 9
j: 4 tab[ 4 ]= 7 - tab[ 5 ]= 5 <->
Algorithme et exemple
Algorithme
def tri_bulle(tab): 3 1 4 2 5 7 9
n = len(tab)
for i in range(0,n):
for j in range(n-i-1):
if tab[j] > tab[j+1] : 3 1 4 2 5 7 9
tmp=tab[j+1]
tab[j+1]=tab[j]
tab[j] = tmp
1 3 4 2 5 7 9
return(tab)
---i: 2 1 3 4 2 5 7 9
j: 0 tab[ 0 ]= 3 - tab[ 1 ]= 1 <->
j: 1 tab[ 1 ]= 3 - tab[ 2 ]= 4
j: 2 tab[ 2 ]= 4 - tab[ 3 ]= 2 <->
j: 3 tab[ 3 ]= 4 - tab[ 4 ]= 5 1 3 2 4 5 7 9
Algorithme et exemple
Algorithme
def tri_bulle(tab): 1 3 2 4 5 7 9
n = len(tab)
for i in range(0,n):
for j in range(n-i-1):
if tab[j] > tab[j+1] : 1 3 2 4 5 7 9
tmp=tab[j+1]
tab[j+1]=tab[j]
tab[j] = tmp
1 3 2 4 5 7 9
return(tab)
---i: 3 1 2 3 4 5 7 9
j: 0 tab[ 0 ]= 1 - tab[ 1 ]= 3
j: 1 tab[ 1 ]= 3 - tab[ 2 ]= 2 <->
j: 2 tab[ 2 ]= 3 - tab[ 3 ]= 4
Algorithme et exemple
Algorithme
def tri_bulle(tab): 1 2 3 4 5 7 9
n = len(tab)
for i in range(0,n):
for j in range(n-i-1):
if tab[j] > tab[j+1] : 1 2 3 4 5 7 9
tmp=tab[j+1]
tab[j+1]=tab[j]
tab[j] = tmp
1 2 3 4 5 7 9
return(tab)
---i: 4
j: 0 tab[ 0 ]= 1 - tab[ 1 ]= 2
j: 1 tab[ 1 ]= 2 - tab[ 2 ]= 3
Algorithme et exemple
Algorithme
def tri_bulle(tab): 1 2 3 4 5 7 9
n = len(tab)
for i in range(0,n):
for j in range(n-i-1):
if tab[j] > tab[j+1] : 1 2 3 4 5 7 9
tmp=tab[j+1]
tab[j+1]=tab[j]
tab[j] = tmp
return(tab)
---i: 5
j: 0 tab[ 0 ]= 1 - tab[ 1 ]= 2
1er algo de tri fusion écrit par Von Neumann pour l’EDVAC en 1945
Importantes contributions:
mécanique quantique, analyse fonctionnelle,sciences économiques,
théorie des ensembles, informatique,
Mathématicien britannique,
Auteur de l'article fondateur de la science informatique:
La machine de Turing et
les concepts modernes de programmation et de programme
Création des calculateurs universels programmables: les ordinateurs.
Après la guerre:
il travaille sur un des tout premiers ordinateurs puis contribue au débat
déjà houleux à cette période sur la capacité des machines à penser en
établissant le test de Turing.
En 1952 un fait divers indirectement lié à son homosexualité lui vaut des
poursuites judiciaires. Pour éviter la prison, il choisit la castration chimique
par prise d'œstrogènes. Il se suicide par empoisonnement au cyanure le 7
juin 1954.
Réabilitation en 2009
Pétition: « Nous soussignés demandons au premier ministre de s'excuser
pour les poursuites engagées contre Alan Turing qui ont abouti à sa mort
prématurée», dressée à l'initiative de l'informaticien John Graham-
Cumming a été envoyée à Gordon Brown.
En septembre 2009, le Premier ministre britannique a présenté des
regrets au nom du gouvernement britannique pour le traitement qui lui a
été inOigé
2. Régner :
Trier les 2 sous-séquences récursivement à l’aide du tri fusion
3. Combiner :
Fusionner les 2 sous-séquences triées pour produire la séquence
triée.
4 6 11 0 7 8 9
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2) 4 0
i1 = 0; i2 = 0; i = 0
while i1<n1 and i2<n2:
if L1[i1] < L2[i2]:
L12[i] = L1[i1] 0
i1 += 1
else:
L12[i] = L2[i2]
4 6 11 7 8 9
i2 += 1
i += 1
while i1<n1:
L12[i] = L1[i1] 4 7
i1 += 1;i += 1
while i2<n2:
L12[i] = L2[i2]
i2 += 1; i += 1 0.4
return(L12)
6 11 7 8 9
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2) 6 7
i1 = 0; i2 = 0; i = 0
while i1<n1 and i2<n2:
if L1[i1] < L2[i2]:
L12[i] = L1[i1] 0.4.6.
i1 += 1
else:
L12[i] = L2[i2]
11 7 8 9
i2 += 1
i += 1
while i1<n1:
L12[i] = L1[i1] 11 7
i1 += 1;i += 1
while i2<n2:
L12[i] = L2[i2]
i2 += 1; i += 1 0.4.6.7.
return(L12)
11 8 9
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2) 11 8
i1 = 0; i2 = 0; i = 0
while i1<n1 and i2<n2:
if L1[i1] < L2[i2]:
L12[i] = L1[i1] 0.4.6.7.8.
i1 += 1
else:
L12[i] = L2[i2]
11 9
i2 += 1
i += 1
while i1<n1:
L12[i] = L1[i1] 11 9
i1 += 1;i += 1
while i2<n2:
L12[i] = L2[i2]
i2 += 1; i += 1 0.4.6.7.8.9.
return(L12)
11
def fusion(L1,L2):
n1 = len(L1)
n2 = len(L2)
L12 = [0]*(n1+n2) 0.4.6.7.8.9.11. .
i1 = 0; i2 = 0; i = 0
while i1<n1 and i2<n2:
if L1[i1] < L2[i2]:
L12[i] = L1[i1]
i1 += 1
else:
L12[i] = L2[i2]
i2 += 1
i += 1
while i1<n1:
L12[i] = L1[i1]
i1 += 1;i += 1
while i2<n2:
L12[i] = L2[i2]
i2 += 1; i += 1
return(L12)
3.4.7 1.2.5.9
1.2.3.4.5.7.9
3.4.7 1.2.5.9
1.2.3.4.5.7.9
2. Régner :
2 sous-tableaux triés grâce à la récursivité
fonction TriRapide
3. Combiner :
2 sous-tableaux triés sur place : Rien à faire
def tri_partition(L,debut,fin):
if debut < fin: 5 3 2 6 4 1 3 7
R= partition(L,debut,fin)
i=R[0];L=R[1]
tri_partition(L,debut,i-1) 5 3 2 1 4 6 3 7
tri_partition(L,i+1,fin)
tri_partition(L,0,len(L)-1) 4 3 2 1 5 6 3 7
def tri_partition(L,debut,fin):
if debut < fin:
R= partition(L,debut,fin)
i=R[0];L=R[1]
tri_partition(L,debut,i-1)
tri_partition(L,i+1,fin)
tri_partition(L,0,len(L)-1)
61 / 80
Tris par comparaisons
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 0 0 0 0 0 0
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 0 0 1 0 0 0
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 0 0 1 0 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 0 0 1 1 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 1 0 1 1 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 1 0 2 1 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 1 0 2 2 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 2 0 2 2 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 2 0 2 3 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 2 0 2 3 0 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 2 0 2 3 0 1
1 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 2 0 2 3 0 1
1 1
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 2 0 2 3 0 1
1 1 3 3
3 6 4 1 3 4 1 4
0 1 2 3 4 5 6
0 2 0 2 3 0 1
1 1 3 3 4 4 4 6
Donc seul les tris qui ont une complexité en O(n log2 n) sont
optimaux.
Le tri fusion est optimal mais pas la version du tri rapide présenté dans
ce cours!
Smoothsort
Tri de Shell
Tri à peigne