1

FORMATION PYTHON : Le TRI en Python

Ce chapitre a pour but d’initier aux algorithmes de tri en Python.

[Link]
aid/
Introduction 2
 Les méthodes de tri sont évidemment fondamentales.
 On dispose de nombreux algorithmes qui se
distinguent par leurs complexités en temps et en place
mémoire.
 Dans ce cours nous allons illustrer quelques-uns de
ces algorithmes avec des listes ou des tableaux
d’entiers (ou de flottants).
 Lorsque le programme contient une boucle while, il ne
faudra pas oublier de s’assurer qu’elle se termine.
 Nous chercherons aussi à estimer le nombre
d’opérations que son exécution entraine : On parle de
calcul de complexité.
[Link]
aid/
Introduction 3

 On considère ici des tableaux ou listes d’entiers ou de

flottants.
 En Python, on peut trier une liste à l’aide de la méthode
sort : si a est une liste d’entiers ou de flottants, [Link]()
modifie la liste en la liste triée.
 En revanche, la fonction sorted(a) est une fonction qui
prenant une liste ou un tableau renvoie la liste (ou le
tableau) des éléments triés par ordre croissant.
 Ainsi : a = [4,1,3,2] ; [Link]() # modifie a en [1, 2, 3, 4]
sorted(a) # renvoie la liste [1, 2, 3, 4]; a inchangée !
[Link]
aid/
Introduction 4

 Une fois triée, une liste peut servir pour d’autres

traitements comme :
 L’insertion d’une nouvelle donnée à sa bonne position
en prenant en considération l’ordre établi ;
 Les algorithmes dichotomiques qui utilisent les listes
triées pour accélérer la recherche…
 On distingue deux grandes catégories de tri :
 Tris lents (par sélection, à bulles, par insertion…)
 et les tris rapides (par fusion, quicksort,…)

[Link]
aid/
Les Tris en Python
1. TRI PAR SELECTION
2. TRI PAR INSERTION
3. TRI RAPIDE
4. TRI FUSION
5. EXERCICES ( TD )
 6

1.
TRI PAR
SELECTION

[Link]
aid/
1. Tri par sélection : Principe 7

 Commencer à chercher l’indice du minimum de la liste L ;

 Permuter le 1er élément de la liste avec l’élément

minimum trouvé ;
 Chercher l’indice du minimum des éléments de la sous
liste L[1 :] et le permuter avec le 2ème élément…
 Continuer ce principe jusqu’à ce que la liste devienne
triée.

 D’une manière générale, on échange l’élément à la

position i avec le minimum de la sous liste L[i+1 :]
[Link]
aid/
 1. Tri par sélection : Exemple 8

Exemple :
L=[4,5,1,-6,2]
 Etape N°1 :
Le minimum de L est -6, on le permute avec 4 : L=[-6,5,1,4,2] ;
 Etape N°2 :
Le minimum de [5,1,4,2] est 1, on le permute avec 5 :
L=[-6,1, 5,4,2]
 Etape N°3 :
Le minimum de [5,4,2] est 2, on le permute avec 5 :
L=[-6,1,2,4,5]
 Etape N°4 : Le minimum de [4,5] est 4, il est à sa bonne place.

[Link]
aid/
1. Tri sélection : Version itérative 10

[Link]
aid/
1. Tri sélection : Version itérative 11

 Complexité

Algorithme Unités de temps

def triselect(L): T(n)=
n=len(L) 1 + 1
for i in range(n-1): n-2 boucles
imin=i 1
for j in range(i+1,n): (n-i-1) boucles
if L[j]<L[imin]: 1
imin=j 1
if i!=imin: 1
L[i],L[imin]=L[imin],L[i] 2

Le nombre de comparaison est donné par (n-i-1)

[Link]
aid/
1. Tri sélection : Version itérative 12
𝑛−2

𝑇 𝑛 = 𝑛 − 1 + 𝑛 − 2 + ⋯+ 2 + 1 = 𝑛−𝑖−1
𝑖=0

 T(n) peut être vu comme la somme de n-1 termes d’une suite

arithmétique de premier terme 1 et de raison 1 :

(𝑛 − 1) 1 + 𝑛 − 1 (𝑛 − 1)𝑛 𝑛2 𝑛
𝑇 𝑛 = = = −
2 2 2 2
 O(T(n))=O(n²) : L’algorithme du tri est quadratique, pas très pratique
quand la taille des données s’accroit.

[Link]
aid/
1. Tri sélection : Version récursive 13

[Link]
aid/
 16

2.
TRI PAR
INSERTION

[Link]
aid/
 2. Tri par insertion : Principe * 17

 On considère une liste ou un tableau dont les premiers

éléments d’indices 0, 1, …, i - 1 sont déjà triés.

 On cherche à placer l’élément d’indice i à sa bonne

place parmi les éléments déjà triés, pour cela on

procède à le comparer aux précédents jusqu’à ce que

la place de T[i] soit trouvée.

[Link]
aid/
2. Tri par insertion : Version itérative 20

[Link]
aid/
2. Tri par insertion : Version itérative 21
Complexité dans le pire de cas :

 Dénombrons les comparaisons entre éléments du tableau

 Dans tous les cas on a n-1 passages dans la boucle for

 Dans la boucle while, le nombre d’itérations est maximal lorsque T

est trié dans l’ordre décroissant, ce qui conduit à i-1 comparaisons.

 Soit en tout, le temps d’exécution est donné par :

𝑛−1 𝑛(𝑛−1) 𝑛2
𝑇 𝑛 = 𝑖=1 𝑖 = 1 + 2 + ⋯+ 𝑛 − 1 = ≈
2 2

 O(T(n))=O(n²)
[Link]
aid/
2. Tri par insertion : Version récursive 22

[Link]
aid/
 25

3.
TRI RAPIDE

[Link]
aid/
3. Tri rapide : Principe * 26
Tri rapide (quicksort) : diviser pour régner
Le principe de ce tri est le suivant :
Pour trier une liste L,
 Si L est vide ou admet un seul élément, elle est triée (c’est notre
critère d’arrêt)
 Sinon :
 On choisit un élément e ϵ L, quelconque, que l’on retire de L ;
 On construit deux sous listes :
 Li formée des éléments inférieurs à e
 Ls formée des éléments plus grands que e
 Le résultat est la concaténation de Li récursivement triée, de [e], et
de Ls qui est aussi récursivement triée.

[Link]
aid/
3. Tri rapide : Version récursive 31

[Link]
aid/
3. Tri rapide : Version récursive 32
Complexité :
 Nous chercherons naturellement à évaluer le nombre
des comparaisons entre les éléments de la liste.
 Considérons un appel principal avec une liste de
longueur n.
 Afin d’identifier le pire de cas, on suppose que l’on
choisisse systématiquement le plus grand élément de la
liste.
 Nous aurons à chaque fois une de deux listes est vide
len(Li)=0 et l’autre liste contenant len(Ls)-1
comparaisons

[Link]
aid/
3. Tri rapide : Version récursive 33
 Les appels récursifs iront deux par deux avec une liste privé
d’un élément par rapport à l’argument d’appel et une liste
vide.

 L’arbre des appels sera la plus haute possible

 Les appels seront les plus couteux en nombre de

comparaisons :
𝑛 𝑛−1
n − 1 + 𝑛 − 2 + ⋯+ 1 = = 𝑂(𝑛2 )
2!
𝑂(𝑛2 ) : complexité au pire de cas
𝑂 𝑛 ln 𝑛 : complexité moyenne
[Link]
aid/
3. Tri rapide : Conclusion 34

 Question :
Qu’est-ce que garantit que le programme se termine ?

 Réponse :
Les appels récursifs ont pour arguments des listes de
longueurs strictement plus petites que len(L).
La condition d’arrêt sera remplie dans tous les cas en un
temps fini (l’arbre des appels est au plus de hauteur len(L))

[Link]
aid/
3. Tri rapide : Conclusion 35
 Question :
Qu’est-ce que garantit que la liste sera finalement triée ?
 Réponse :
Si len(L) = 0 ou len(L)=1, le résultat est clair ;
Sinon,
Supposons que la propriété est vraie pour les listes de longueurs 0,1,
…, n.
Les deux appels récursifs ont comme paramètre des sous-listes de L\{e}
Elles retournent donc par hypothèse de récurrence deux copies triées
de Li et Ls.
La concaténation de trois listes Li,[e] et Ls est donc triée.
Avec e (le pivot) est plus grand que les éléments de Li et plus petit que
les éléments de Ls.
[Link]
aid/
 36

4.
TRI FUSION

[Link]
aid/
4. Tri fusion : Principe * 37
Le tri fusion est défini de la façon suivante :
 Le critère d’arrêt : Le tableau a au plus un élément (il est déjà trié)
 Si le tableau a plus d’un élément, on appelle récursivement la
fonction sur chacun des sous-tableaux et on interclasse leurs copies
triées
 Pour rassembler deux tableaux T1 et T2 déjà triés, on peut les
interclasser de la façon suivante :
 On compare les plus petits éléments de chacun d’eux, on place le
plus petit d’eux dans un nouveau tableau T.
 On poursuit en comparent successivement les deux plus petits
éléments non encore trié de ces tableaux jusqu’à l’épuisement de
l’un d’eux, il ne reste plus qu’ajouter les éléments du tableau non
vidé.

[Link]
aid/
4. Tri fusion : Version récursive 43

[Link]
aid/
4. Tri fusion : Conclusion 44
Inconvénients:
 C’est n’est pas un tri en place, car il réserve un nouveau
tableau de même taille que le tableau à trier.

 Un tri qui n’utilise pas de mémoire supplémentaire est un

tri en place (puisque les éléments sont échangés dans le
tableau ou la liste, sur place)

[Link]
aid/