Cours complexité – algorithmique (DSSD)
Cours 4: Applications de la complexité des
algorithmes récursifs: Algorithmes de tri
Dr. Dhouha Maatar Razgallah
2019/2020
Outline
Tri par sélection
Tri par insertion
Tri à bulles
Tri rapide
Tri Fusion
1
Algorithmes de tri Tri par Sélection
Algorithmes de tri Tri par Sélection
2
Algorithmes de tri Tri par Sélection
Algorithmes de tri Tri par Sélection
3
Algorithmes de tri Tri par Insertion
Algorithmes de tri Tri par Insertion
4
Algorithmes de tri Tri par Insertion
Algorithmes de tri Tri par Insertion
10
5
Algorithmes de tri Tri à bulles
11
Algorithmes de tri Tri à bulles
12
6
Algorithmes de tri Tri à bulles
13
Algorithmes de tri Tri à bulles
14
7
Algorithmes de tri Tri rapide
Tri rapide
Principe:
Le principe consiste à choisir un élément du tableau, appelé Pivot ( par exemple la
première valeur du tableau) qui va servir à partitionner ce tableau en deux parties.
Toutes les valeurs d'une partie seront inférieures au Pivot, les autres supérieures.
Ensuite, de façon récursive, l'algorithme va recommencer le tri dans les deux sous
tableaux ainsi obtenus.
Le tri rapide est fondé sur le paradigme ‘’diviser pour régner’’.
Exemple:
15
Algorithmes de tri Tri rapide
Tri rapide
Paradigme ‘’diviser pour régner’’:
Diviser: le tableau initial est partitionné (et réarrangé) en deux sous-tableaux
selon le pivot choisi: T1[debut..pivot] et T2[pivot+1..fin].
L’indice pivot est calculé pendant la procédure de partitionnement.
Régner: trier (par tri rapide) les deux tableaux par des appels récursifs.
Combiner: combiner les deux tableaux:
T[debut..fin] = T1[debut..pivot] + T2[pivot+1..fin] est trié
16
8
Algorithmes de tri Tri rapide
Algorithme récursif: Fonction ‘’partitionner’’
Procédure Tri_rapide (varT:tab; deb, fin: entier) partitionner (T:tab; deb, fin, piv: entier): entier
Var Pivot : entier Var i, j : entier
Début Début
si (deb<fin) alors permuter (T[piv], T[fin])
Pivot← partitionner (T,deb,fin, piv) j← deb
Tri_rapide (deb, Pivot) pour i de 1 à fin-1 faire
Tri_rapide (Pivot+1, fin) Si (T[i] <= T[fin])alors
Finsi permuter (T[i], T[j])
Fin j←j+1
Finsi
Finpour
permuter (T[fin], T[j])
retourner j
Fin
17
Algorithmes de tri Tri rapide
Tri rapide
Complexité de ‘’partitionner’’
fonction partitionner (T:tab; deb, fin, piv: entier): entier
T partitionner (n)tq n= fin-deb+1
Var i, j : entier
Début
permuter (T[piv], T[fin])
j← deb
pour i de 1 à fin-1 faire
Si (T[i] <= T[fin])alors
permuter (T[i], T[j])
Pire de cas: n-1 fois
j←j+1
Finsi
Finpour
permuter (T[fin], T[j])
retourner j
Fin
O(T partitionner (n))= O(n) 18
9
Algorithmes de tri Tri rapide
Tri rapide
Complexité
Procédure Tri_rapide (varT:tab; deb, fin: entier)
Var Pivot : entier
Début
si (deb<fin) alors
Pivot← partitionner (T,deb,fin, piv) T partitionner (n)
Tri_rapide (deb, Pivot)
Tri_rapide (Pivot+1, fin) T (Pivot-deb +1)
Finsi T (fin - Pivot )
Fin
T(n) = T (Pivot-deb +1)+ T (fin - Pivot )+T partitionner (n)
19
Algorithmes de tri Tri rapide
Tri rapide
Choix du pivot et Complexité
Pire des cas:
Le cas pire intervient lorsque le partitionnement (choix du pivot) produit une région à n-1 éléments et
une à 1 élément :
T(n) = T (n-1)+ T (1)+T partitionner (n)
O(T(n)) = O(T (n-1))+O( T (1))+O(T partitionner (n))
O(T(n)) = O(T (n-1))+O( 1)+O(n)
Par sommation on obtient :
Le meilleur cas:
Il intervient lorsque le partitionnement produit deux régions de longueurs n/2.
La récurrence est alors définie par:
T(n) = 2 T (n/2)+O(T partitionner (n))
T(n) = 2 T (n/2)+ c n
Conformément au théorème de récurrence du paradigme ‘’diviser pour régner’’ : a =2, b=2, k=1 donc
a=b d’où O(T(n)) = O (n log₂ n) 20
10
Algorithmes de tri Tri par fusion
Tri par fusion
Principe:
Le principe consiste à trier deux tableaux de taille n/2 et ensuite de les fusionner
de sorte que le tableau final soit trié. Ce tri utilise une notion de récursivité (un
tableau est la somme de deux tableaux).
Le tri fusion est construit suivant la stratégie ‘’diviser pour régner’’.
Exemple:
21
Algorithmes de tri Tri par fusion
Tri par fusion
Paradigme ‘’diviser pour régner’’:
Diviser: le tableau initial en deux sous-tableaux de même taille:
T[debut..fin] = T1[debut..milieu] +T2[milieu+1..fin].
Régner: trier (par fusion) les deux tableaux par des appels récursifs.
Combiner: combiner les deux tableaux de façon que le tableau T reste trié.
22
11
Algorithmes de tri Tri par fusion
Algorithme récursif: Procédure ‘’Fusionner’’
Procédure Tri_fusion (varT:tab; deb, fin: entier) fusionner (var T:tab; deb, milieu, fin: entier)
Var milieu : entier Var i, gauche, droite : entier
Début Tmp: tab
si (deb<fin) alors Début
milieu← (deb + fin)/2 i ← deb; gauche ← deb; droite ← milieu +1;
Tri_fusion (T,deb, milieu) Tant que ( i<= fin) faire
Tri_fusion (T,milieu+1, fin) Si ((gauche <= milieu) et (T[gauche] <T[droite]))
Fusionner (T,deb, milieu, fin) ou (droite > fin)) alors
Finsi Tmp[i] ← T[gauche]
Fin gauche ++
Sinon
Tmp[i] ← T[droite]
droite ++
Finsi
i++
Fintq
Pour i de deb à fin faire
T[i] ← Tmp[i]
23
finpour
Fin
Algorithmes de tri Tri fusion
Tri fusion
Complexité de ‘’fusionner’’
procédure fusionner (var T:tab; deb, milieu, fin: entier)
Var i, gauche, droite : entier T fusionner (n) tq n= fin-deb+1
Tmp: tab
Début
i ← deb; gauche ← deb; droite ← milieu +1;
Tant que ( i<= fin) faire
Si ((gauche <= milieu) et (T[gauche] <T[droite]))
ou (droite > fin)) alors
Tmp[i] ← T[gauche]
gauche ++
Sinon n fois
Tmp[i] ← T[droite]
droite ++
Finsi
O(T fusionner (n))= O(n)
i++
Fintq
Pour i de deb à fin faire
T[i] ← Tmp[i] n fois 24
Finpour Fin
12
Algorithmes de tri Tri fusion
Tri fusion
Complexité
Procédure Tri_fusion (varT:tab; deb, fin: entier)
Var milieu : entier
Début
si (deb<fin) alors
milieu← (deb + fin)/2
Tri_fusion (T, deb, milieu) T (n/2)
Tri_fusion (T, milieu+1, fin) T (n/2 )
Fusionner (T,deb, milieu, fin)
T fusionner (n)
Finsi
Fin
T(n) = 2 T (n/2 )+T fusionner (n)
T(n) = 2 T (n/2 )+ c n
Conformément au théorème de récurrence du paradigme ‘’diviser pour régner’’ :
a =2, b=2, k=1 donc
a=b d’où O(T(n)) = O (n log₂ n) 25
13
