Fiche Tris (Python) : sélection, bulles, insertion, rapide, fusion
Notations et rappels
On note n = len(L) la taille de la liste. Les tris sélection, bulles et insertion modifient L (en
place). Les tris rapide et fusion renvoient une nouvelle liste.
1 Tri par sélection – Version min + index
1.1 Idée
À chaque étape i, on cherche le minimum dans la partie non triée L[i:] puis on l’échange avec
L[i]. [web :105]
1.2 Code Python
1 def tri_selection_1(L):
2 for i in range((len(L)) - 1):
3 imin = [Link](min(L[i:]))
4 L[i], L[imin] = L[imin], L[i]
1.3 Explication étape par étape (pourquoi)
— for i in range(len(L)-1) : on place un élément correct à la position i (de 0 à n−2). [web :105]
— min(L[i:]) : trouve la plus petite valeur dans la zone non triée L[i:]. [web :105]
— [Link](x) : renvoie l’indice de la première occurrence de x dans la liste. [web :24]
— Swap : on met le minimum en position i (on agrandit la zone triée). [web :105]
1.4 Complexité
— Temps (meilleur/moyen/pire) : O(n2 ). [web :105]
— Mémoire : O(1). [web :105]
2 Tri par sélection – Version classique (sans index)
2.1 Idée
À l’étape i, on parcourt L[i:] pour trouver l’indice du minimum, puis on fait un seul échange.
[web :105]
2.2 Code Python
1
1 def tri_selection_classique(L):
2 n = len(L)
3 for i in range(n - 1):
4 imin = i
5 for j in range(i + 1, n):
6 if L[j] < L[imin]:
7 imin = j
8 L[i], L[imin] = L[imin], L[i]
2.3 Explication étape par étape (pourquoi)
— imin = i : on suppose que le minimum est au début de la zone non triée. [web :105]
— La boucle en j cherche un plus petit élément que L[imin]. [web :105]
— Après la boucle, imin est l’indice du minimum de L[i:] puis on échange avec L[i]. [web :105]
2.4 Complexité
— Temps (meilleur/moyen/pire) : O(n2 ). [web :105]
— Mémoire : O(1). [web :106]
3 Tri à bulles (parcours décroissant)
3.1 Idée
On compare des voisins et on échange si nécessaire ; en répétant, on finit par obtenir une liste triée.
[web :84][web :118]
3.2 Code Python
1 def tri_a_bulles(L):
2 n = len(L)
3 for i in range(n - 1):
4 for j in range(n - 1, i, -1):
5 if L[j] < L[j - 1]:
6 L[j], L[j - 1] = L[j - 1], L[j]
3.3 Explication étape par étape (pourquoi)
— i compte les passes. [web :84]
— j descend de n-1 vers i+1 : on compare L[j-1] et L[j]. [web :118]
— Si L[j] < L[j-1], on échange : on corrige l’ordre local. [web :84]
3.4 Complexité
— Dans cette version (sans arrêt anticipé) : meilleur/moyen/pire O(n2 ). [web :118]
— Mémoire : O(1). [web :110]
4 Tri par insertion
4.1 Idée
On construit une partie gauche déjà triée ; à l’étape i, on insère L[i] à sa bonne place en décalant
vers la droite les éléments trop grands. [web :125][web :126]
2
4.2 Code Python
1 def tri_insertion(L):
2 for i in range(1, len(L)):
3 c = L[i] # element a inserer
4 j = i - 1
5 while j >= 0 and L[j] > c:
6 L[j + 1] = L[j] # decalage vers la droite
7 j = j - 1
8 L[j + 1] = c
4.3 Explication étape par étape (pourquoi)
— for i in range(1, len(L)) : L[0] est déjà triée, puis on insère les éléments suivants. [web :126]
— c = L[i] : on sauvegarde l’élément courant (clé) avant les décalages. [web :125]
— while ... : tant que L[j] > c, on décale L[j] vers la droite pour faire de la place. [web :125]
— L[j+1] = c : insertion au bon endroit. [web :125]
4.4 Complexité
— Meilleur cas : O(n). [web :133]
— Cas moyen : O(n2 ). [web :133]
— Pire cas : O(n2 ). [web :133]
— Mémoire : O(1). [web :125]
5 Tri rapide (QuickSort) – version récursive
5.1 Idée
On choisit un pivot, on sépare en deux sous-listes (plus petits / plus grands ou égaux), on trie
récursivement, puis on concatène. [web :193][web :192]
5.2 Code Python
1 def tri_rapide(L):
2 if len(L) <= 1:
3 return L
4 p = L[0] # pivot
5 L1 = [] # elements < p
6 L2 = [] # elements >= p
7 for x in L[1:]:
8 if x < p:
9 [Link](x)
10 else:
11 [Link](x)
12 return tri_rapide(L1) + [p] + tri_rapide(L2)
5.3 Explication étape par étape (pourquoi)
— Cas de base : si len(L) <= 1, la liste est déjà triée. [web :193]
— Partition : on parcourt la liste et on met chaque élément dans L1 ou L2. [web :193]
— Récursivité + concaténation : la liste finale est tri(L1) + [p] + tri(L2). [web :193]
3
5.4 Complexité
— Meilleur cas : O(n log n). [web :192]
— Cas moyen : O(n log n). [web :192]
— Pire cas : O(n2 ) (partitions très déséquilibrées). [web :192]
6 Tri fusion (MergeSort) + fonction fusion
6.1 Idée
tri_fusion découpe la liste en deux moitiés, trie récursivement, puis fusion combine deux listes
déjà triées en une liste triée. [web :274]
6.2 Code Python
1 def fusion(L1, L2):
2 if L1 == []:
3 return L2
4 if L2 == []:
5 return L1
6 if L1[0] < L2[0]:
7 return [L1[0]] + fusion(L1[1:], L2)
8 else:
9 return [L2[0]] + fusion(L1, L2[1:])
10
11 def tri_fusion(L):
12 if len(L) <= 1:
13 return L
14 m = len(L) // 2
15 return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))
6.3 Explication étape par étape (pourquoi)
— tri_fusion : découpe en deux moitiés, trie chaque moitié, puis fusionne. [web :274]
— fusion : compare les deux premiers éléments L1[0] et L2[0], met le plus petit en tête, puis
continue récursivement. [web :274]
— Cas de base de fusion : si une liste est vide, on renvoie l’autre (déjà triée). [web :274]
6.4 Complexité
— Meilleur cas : O(n log n). [web :274]
— Cas moyen : O(n log n). [web :274]
— Pire cas : O(n log n). [web :274]
Récapitulatif des complexités (temps)
Algorithme Meilleur cas Cas moyen Pire cas
Sélection (classique) O(n2 ) [web :105] O(n2 ) [web :105] O(n2 ) [web :105]
Sélection (min+index) O(n2 ) [web :105] O(n2 ) [web :105] O(n2 ) [web :105]
Bulles (sans arrêt anticipé) O(n2 ) [web :118] O(n2 ) [web :118] O(n2 ) [web :118]
Insertion O(n) [web :133] O(n2 ) [web :133] O(n2 ) [web :133]
Rapide (QuickSort) O(n log n) [web :192] O(n log n) [web :192] O(n2 ) [web :192]
Fusion (MergeSort) O(n log n) [web :274] O(n log n) [web :274] O(n log n) [web :274]