Les Algorithmes de Tri

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 81

Les algorithmes de tris

Chargée de cours: Lélia Blin

Email: lelia.blin@lip6.fr

Transparents : http://www-npa.lip6.fr/~blin/Enseignements.html

Blin Lélia (Univ. Evry) 1 / 80


Idée fondamentale

On considère une collection d'entier placés dans un tableau

Un opérateur de comparaison (≤,≥, >, <, …)

But :
Ré-ordonner les valeurs de la façon suivante
T [i] ≤ T [i + 1]∀i ∈ [1..T aillemax]

Blin Lélia (Univ. Evry) 2 / 80


Quelques algorithmes de tris
Tris élémentaires
Tri par insertion

Tri par sélection

Tri par permutation

Tris avancés
Tri Fusion

Tri rapide

Blin Lélia (Univ. Evry) 3 / 80


Tris élémentaires
Tri interne, sur place et par comparaison

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

Blin Lélia (Univ. Evry) 4 / 80


Tri par insertion

Blin Lélia (Univ. Evry) 5 / 80


Tri insertion

C’ est un algorithme eQcace quand il


s’agit de trier un petit nombre
d’éléments.
Le tri par insertion s’inspire de la manière
dont la plupart des gens tiennent des
cartes à jouer.

Blin Lélia (Univ. Evry) 6 / 80


Tri insertion
Tri des cartes à jouer:
Au début, la main gauche du joueur est vide
et ses cartes sont posées sur la table.
Le joueur prend alors sur la table les cartes,
une par une, pour les placer dans sa main
gauche.
Pour savoir où placer une carte dans son jeu,
le joueur la compare avec chacune des
cartes déjà présentes dans sa main gauche,
en examinant les cartes de la droite vers la
gauche
A tout moment, les cartes tenues par la main
gauche sont triées ;

Blin Lélia (Univ. Evry) 7 / 80


Tri insertion principe

Prendre un élément non encore trié

L’insérer à sa place dans l’ensemble des éléments triés

Blin Lélia (Univ. Evry) 8 / 80


Tri par insertion

Algorithme et exemple
Algorithme Exemple

def tri_insertion(L): Liste initiale


n =len(L)
for i in range(1,n):
cle = L[i]
7 4 3 1 9 2 5
j = i-1
while j>=0 and L[j] > cle:
L[j+1] = L[j] cle: 4 , j: 1
j = j-1
L[j+1] = cle
return(L) 7 4 3 1 9 2 5

7 7 3 1 9 2 5

4 7 3 1 9 2 5

Blin Lélia (Univ. Evry) 9 / 80


{'nodeSpacing': 5, 'rankSpacing':
Tri par insertion
# Algorithme et exemple
Algorithme
Exemple
def tri_insertion(L):
n =len(L) cle: 3 , j: 2
for i in range(1,n):
cle = L[i]
j = i-1
while j>=0 and L[j] > cle: 4 7 3 1 9 2 5
L[j+1] = L[j]
j = j-1
L[j+1] = cle 4 7 7 1 9 2 5
return(L)

4 4 7 1 9 2 5

3 4 7 1 9 2 5

Blin Lélia (Univ. Evry) 10 / 80


Tri par insertion

Algorithme et exemple
Algorithme Exemple

def tri_insertion(L): cle: 1 , j: 2


n =len(L)
for i in range(1,n):
cle = L[i] 3 4 7 1 9 2 5
j = i-1
while j>=0 and L[j] > cle:
L[j+1] = L[j]
j = j-1 3 4 7 7 9 2 5
L[j+1] = cle
return(L)
3 4 4 7 9 2 5

3 3 4 7 9 2 5

1 3 4 7 9 2 5

Blin Lélia (Univ. Evry) 11 / 80


Tri par insertion

Algorithme et exemple
Algorithme Exemple

def tri_insertion(L): cle: 9 , j: 3


n =len(L)
for i in range(1,n):
cle = L[i] 1 3 4 7 9 2 5
j = i-1
while j>=0 and L[j] > cle:
L[j+1] = L[j]
j = j-1 1 3 4 7 9 2 5
L[j+1] = cle
return(L)

Blin Lélia (Univ. Evry) 12 / 80


Tri par insertion

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

Blin Lélia (Univ. Evry) 13 / 80


Tri par insertion

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

Blin Lélia (Univ. Evry) 14 / 80


Tri par insertion

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].

Maintenant les éléments de L[1..j − 1] sont triés.


On veut maintenir cet: invariant de boucle

Blin Lélia (Univ. Evry) 15 / 80


Tri par insertion

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.

Blin Lélia (Univ. Evry) 16 / 80


Tri par insertion

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.

Blin Lélia (Univ. Evry) 17 / 80


Tri par insertion

Invariant de boucle: Initialisation


Montrons que l’invariant est véri[é avant la première itération de la boucle

Autrement dit quand j = 2.


Le sous-tableau L[1..j − 1] se compose donc uniquement de l’élément L[1]
En outre, ce sous-tableau est trié (c’est une trivialité),
Cela montre que l’invariant est véri[é avant la première itération de la
boucle.

Blin Lélia (Univ. Evry) 18 / 80


Tri par insertion

Invariant de boucle: Conservation


Montrons que chaque itération conserve l’invariant

De manière informelle le corps de la boucle for fonctionne:


en déplaçant L[j − 1], L[j − 2], L[j − 3], etc.
d’une position vers la droite
jusqu’à ce qu’on trouve la bonne position pour L[j],
auquel cas on insère la valeur de L[j].

Blin Lélia (Univ. Evry) 19 / 80


Tri par insertion

Invariant de boucle : Terminaison


Examinon se qui se passe à la terminaison de la boucle

la boucle for prend [n quand j dépasse n (c’est-à-dire quand j = n + 1).


Substituons n + 1 à j dans la formulation de l’invariant de boucle.
On obtient le sous-tableau L[1..n] composait des éléments qui appartenaient
originellement à L[1..n] mais qui ont été triés depuis lors.
Or, le sous-tableau L[1..n] n’est autre que le tableau complet !
Par conséquent, le tableau tout entier est trié, donc l’algorithme est correct.

Blin Lélia (Univ. Evry) 20 / 80


Tri par insertion

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

= l1 + nl2 (l3 + l4 + nl5 (l6 + l7 ) + l8 ) + l9

= (l1 + l9 ) + n(l3 + l4 + l8 ) + n2 (l6 + l7 ) → O(n2 )

Blin Lélia (Univ. Evry) 21 / 80


Tri par selection

Blin Lélia (Univ. Evry) 22 / 80


Tri par selection
Principe général :
Tableau toujours divisé en 2 parties

A chaque étape,
Choisir le plus petit élément de la partie non triée

Mettre cet élément à la [n de la partie triée

Blin Lélia (Univ. Evry) 23 / 80


Tri selection

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

Blin Lélia (Univ. Evry) 24 / 80


Tri selection

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

Blin Lélia (Univ. Evry) 25 / 80


Tri selection

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

Blin Lélia (Univ. Evry) 26 / 80


Tri selection

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

Blin Lélia (Univ. Evry) 27 / 80


Tri selection

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

Blin Lélia (Univ. Evry) 28 / 80


Tri selection

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

Blin Lélia (Univ. Evry) 29 / 80


Tri selection

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

Blin Lélia (Univ. Evry) 30 / 80


Complexité du tri par selection
Nombre d’itérations : n − 1

A chaque itération :
Recherche du minimum : n − T ( T taille courante)

Mettre l’élément à sa place : 3

Au total : 3n + n(n − 1)/2

Complexité : O(n2 )

Blin Lélia (Univ. Evry) 31 / 80


Tri par permutation
Tri à bulles

Blin Lélia (Univ. Evry) 32 / 80


Tri par permutation
Pincipe:
Si 2 éléments voisins ne sont pas
ordonnés on les échange
Deux parties dans le tableau :
Les éléments de la partie triée

sont inférieurs

aux éléments de la partie non triée.

Blin Lélia (Univ. Evry) 33 / 80


Tri permutation

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 <->

Blin Lélia (Univ. Evry) 34 / 80


Tri permutation

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 <->

Blin Lélia (Univ. Evry) 35 / 80


Tri permutation

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

Blin Lélia (Univ. Evry) 36 / 80


Tri permutation

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

Blin Lélia (Univ. Evry) 37 / 80


Tri permutation

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

Blin Lélia (Univ. Evry) 38 / 80


Tri permutation

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

Blin Lélia (Univ. Evry) 39 / 80


Complexité tri permutation
Boucle externe : n − 2 fois

Boucle interne : n − T fois

Total : (n − 1)(n − 2)/2


2
Complexité O(n )

Blin Lélia (Univ. Evry) 40 / 80


Les tris avancés

Blin Lélia (Univ. Evry) 41 / 80


Le tri fusion
Machine à trier des cartes perforées en 1938

1er algo de tri fusion écrit par Von Neumann pour l’EDVAC en 1945

Basé sur le paradigme « Diviser pour Régner »

Blin Lélia (Univ. Evry) 42 / 80


John von Neumann (1903-1957)
.

Mathématicien et physicien américano-hongrois.

Importantes contributions:
mécanique quantique, analyse fonctionnelle,sciences économiques,
théorie des ensembles, informatique,

Il a de plus participé aux programmes militaires américains.


Architecture de Von Neuman:
possède une unique mémoire qui sert à conserver les logiciels et les
données.
utilisée dans la quasi totalité des ordinateurs modernes.

Blin Lélia (Univ. Evry) 43 / 80


Alan Mathison Turing (1912-1954)
.

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.

Pere de l’informatique : Il est également à l'origine:


de la formalisation des concepts d'algorithme et
de calculabilité qui ont profondément marqué cette discipline.
Thèse de Church-Turing : Son modèle a contribué à établir dé[nitivement
la thèse Church-Turing qui donne une dé[nition mathématique au
concept intuitif de fonction calculable.
Blin Lélia (Univ. Evry) 44 / 80
Alan Mathison Turing (1912-1954)
Durant la Seconde Guerre mondiale:
Il joue un rôle majeur dans les recherches sur les cryptographies générées
par la machine Enigma utilisée par les nazis.

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.

Blin Lélia (Univ. Evry) 45 / 80


Alan Mathison Turing (1912-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é

Blin Lélia (Univ. Evry) 46 / 80


PRIX TURING

Depuis 1966 le prix Turing est annuellement décerné par l'Association


for Computing Machinery à des personnes ayant apporté une
contribution scientiique signiicative à la science de l'informatique.
Cette récompense est souvent considérée comme l'équivalent du prix
Nobel de l'informatique.

Blin Lélia (Univ. Evry) 47 / 80


Diviser pour Régner

Séparer le problème en plusieurs sous-problèmes similaires au problème


initial
1. Diviser : le pb en un certain nombre de sous-pb

2. Régner : sur les sous-pbs en les résolvant

3. Combiner : les solutions des sous-pbs en une solution unique.

Blin Lélia (Univ. Evry) 48 / 80


Le tri par fusion : Diviser pour Régner
1. Diviser :
la séquence de n éléments à trier en 2 sous-séquences de n/2
éléments, jusqu'à que chaque sous-séquence soit de taille 1

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.

Blin Lélia (Univ. Evry) 49 / 80


Fusion
Algorithme

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)

Blin Lélia (Univ. Evry) 50 / 80


Fusion
Algorithme

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)

Blin Lélia (Univ. Evry) 51 / 80


Fusion
Algorithme

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)

Blin Lélia (Univ. Evry) 52 / 80


Fusion
Algorithme

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)

Blin Lélia (Univ. Evry) 53 / 80


Tri fusion
7.4.3.1.9.2.5
Algorithme
L1 L2
def tri_fusion(L):
n = len(L) 7.4.3 1.9.2.5
if n > 1:
p = n // 2 L2 L1 L2
L1 = L[:p]
L2 = L[p:n]
4.3 1.9 2.5
tri_fusion(L1)
tri_fusion(L2)
L[:] = fusion(L1,L2) L1 L1 L2 L1 L2 L1 L2
return(L)
4 3 1 9 2 5

7 3.4 1.9 2.5

3.4.7 1.2.5.9

1.2.3.4.5.7.9

Blin Lélia (Univ. Evry) 54 / 80


Tri fusion
7.4.3.1.9.2.5
Algorithme
L1 L2
def tri_fusion(L):
n = len(L) 7.4.3 1.9.2.5
if n > 1:
p = n // 2 L2 L1 L2
L1 = L[:p]
L2 = L[p:n]
4.3 1.9 2.5
tri_fusion(L1)
tri_fusion(L2)
L[:] = fusion(L1,L2) L1 L1 L2 L1 L2 L1 L2
return(L)
4 3 1 9 2 5

Dans quel ordre sont fait


7 3.4 1.9 2.5
les calculs par l'ordinateur?

3.4.7 1.2.5.9

1.2.3.4.5.7.9

Blin Lélia (Univ. Evry) 55 / 80


Complexité du tri par fusion

La preuve est technique mais intuitivement il faut résoudre :


T ri(n) = 2 ∗ T ri(n/2) + Θ(n)

Complexité [nale : O(n log2 n)

Blin Lélia (Univ. Evry) 56 / 80


Le tri rapide : Diviser pour Régner
Proposé par Hoare en 1962
1. Diviser :
T [p..r] est divisé en 2 sous-tableaux non vide T [p..q] et T [q + 1..r]
∀i ∈ T [p..q] et ∀j ∈ T [q + 1..r] on a i < j
fonction Partitionner

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

Blin Lélia (Univ. Evry) 57 / 80


Tri rapide
def partition(L,p,q): 0 1 2 3 4 5 6 7
pivot = L[p];i = p;j = q
while j>i: 5 8 2 6 4 1 3 7
if L[j] < pivot:
if L[i]> pivot:
L[i],L[j] = L[j],L[i]
i += 1 5 8 2 6 4 1 3 7
else:
j -= 1
L[p],L[j] = L[j],L[p]
return(i,L) 5 3 2 6 4 1 8 7

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

Blin Lélia (Univ. Evry) partition [5, 8, 2, 6, 4, 1, 3, 7] 0 758 / 80


Tri rapide
def partition(L,p,q):
pivot = L[p];i = p;j = q
while j>i:
if L[j] < pivot:
if L[i]> pivot:
L[i],L[j] = L[j],L[i]
i += 1
else:
j -= 1
L[p],L[j] = L[j],L[p]
return(i,L)

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)

Blin Lélia (Univ. Evry) 59 / 80


Tri Rapide : Complexité
Dépend de l’équilibre ou non du partitionnement.

Si le partitionnement est équilibré :

aussi rapide que le tri fusion

Si le partitionnement est déséquilibré :

aussi lent que le tri par insertion

Blin Lélia (Univ. Evry) 60 / 80


Partitionnement dans le pire cas
2 sous-tableaux de :
1 élément
n − 1 éléments

Supposons que ce partitionnement intervienne à chaque étape.

Le partitionnement coûte Θ(n)


La récurrence :
T (n) = T (n − 1) + Θ(n)
T (1) = Θ(1)
T (n) = ΣO(k) = O(Σk) = O(n2 )

Ce partitionnement apparaît quand le tableau est trié !!!!

Pire dans ce cas là le tri par insertion est linéaire !!

61 / 80
Tris par comparaisons

Tous les tris vu dans ce cours sont tris par comparaisons

un tri par comparaison est un tri dans lequel on compare


une paire d’éléments.

Existe-t-il des tris qui ne sont pas par comparaisons?

Blin Lélia (Univ. Evry) 62 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 0 0 0 0 0 0

soit B le tableau trié

Blin Lélia (Univ. Evry) 63 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 0 0 1 0 0 0

soit B le tableau trié

Blin Lélia (Univ. Evry) 64 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 0 0 1 0 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 65 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 0 0 1 1 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 66 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 1 0 1 1 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 67 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 1 0 2 1 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 68 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 1 0 2 2 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 69 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 2 0 2 2 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 70 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 2 0 2 3 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 71 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 2 0 2 3 0 1

soit B le tableau trié

Blin Lélia (Univ. Evry) 72 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 2 0 2 3 0 1

soit B le tableau trié

1 1

Blin Lélia (Univ. Evry) 73 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 2 0 2 3 0 1

soit B le tableau trié

1 1

Blin Lélia (Univ. Evry) 74 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 2 0 2 3 0 1

soit B le tableau trié

1 1 3 3

Blin Lélia (Univ. Evry) 75 / 80


Tri linéaire: tri par dénombrement
soit A un tableau d’entier inférieur ou égal à 6

3 6 4 1 3 4 1 4

soit C un tableau qui compte le nombre de fois qu’apparaît un entier

0 1 2 3 4 5 6

0 2 0 2 3 0 1

soit B le tableau trié

1 1 3 3 4 4 4 6

Blin Lélia (Univ. Evry) 76 / 80


Optimalité des tris vus en cours

La borne inférieure pour un tri par comparaison est: Ω(n log2 n)

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!

Blin Lélia (Univ. Evry) 77 / 80


Récapitulatif
Algorithme O Ω Principe
Prendre un élément non encore trié,
Insertion O(n2 ) Ω(n)
l’insérer à sa place dans les éléments triés
Choisir le plus petit élément de la partie
Sélection O(n2 ) non triée, le mettre à la [n de la partie
triée
Si 2 éléments voisins ne sont pas ordonnés
Permutation O(n2 )
on les échange
On divise le tableau en élément plus petit,
Fusion O(n log2 n)
les tableaux sont triés à la reconstruction
Utilisation d'un pivot, les éléments sont
Rapide O(n2 ) Ω(n log2 n)
triés en séparants les listes

Blin Lélia (Univ. Evry) 78 / 80


Autres tris
Tri cocktail

Tri par tas

Smoothsort

Tri de Shell

Tri à peigne

Blin Lélia (Univ. Evry) 79 / 80


Livre conseillé

Blin Lélia (Univ. Evry) 80 / 80

Vous aimerez peut-être aussi