Le tri des données est une opération essentielle en informatique, utilisée pour résoudre divers problèmes pratiques. Cet article présente dix algorithmes de tri classiques en Python, classés par catégories : tri par insertion, tri par sélecsion, tri par échange, tri par fusion et tri par compartiment. Chaque méthode est analysée en termes de copmlexité temporelle et spatiale, ainsi que de stabilité. Un tri est stable si, pour deux éléments égaux a[i] et a[j] avec i < j, leur ordre relatif est préservé après le tri.
- Tri par insertion directe
L'idée est d'insérer chaque élément dans la séquence ordonnée existante. Par exemple, pour la liste [6,8,1,4,3,9,5,0] en ordre croissant, on commence par comparer et déplacer les éléments pour maintenir l'ordre. Ce tri est stable, avec une complexité spatiale O(1) et une complexité temporelle optimale O(n). Voici une implémentation en Python avec des noms de variables modifiés :
def tri_insertion_directe(seq):
for i in range(1, len(seq)):
valeur = seq[i]
j = i - 1
while j >= 0 and seq[j] > valeur:
seq[j + 1] = seq[j]
j -= 1
seq[j + 1] = valeur
return seq
- Tri par insertion binaire
Cette méthode optimise le tri par insertion en utilisant une recherche binaire pour trouver la position d'insertion. Elle réduit le nombre de comparaisons mais conserve la même complexité spatiale O(1). Le code ci-dessous illustre cette approche avec une structure différente :
def tri_insertion_binaire(arr):
for i in range(1, len(arr)):
key = arr[i]
low, high = 0, i - 1
while low < high:
mid = (low + high) // 2
if arr[mid] > key:
high = mid
else:
low = mid + 1
for j in range(i, low, -1):
arr[j] = arr[j - 1]
arr[low] = key
return arr
- Tri de Shell
Basé sur le tri par insertion, le tri de Shell utilise des intervalles décroissants pour grouper et trier les éléments. Par exemple, avec un intervalle initial de la moitié de la longueur de la liste, il améliore l'efficacité en permettant des mouvements sur de longues distances. Ce tri est instable avec une complexité spatiale O(1). L'implémentation suivante utilise des boucles et variables différentes :
def tri_shell(liste):
ecart = len(liste) // 2
while ecart > 0:
for depart in range(ecart):
for k in range(depart, len(liste), ecart):
temp = liste[k]
pos = k
while pos >= ecart and liste[pos - ecart] > temp:
liste[pos] = liste[pos - ecart]
pos -= ecart
liste[pos] = temp
ecart //= 2
return liste
- Tri par sélection directe
Ce tri sélectionne itérativement le minimum de la séquence non triée et l'échange avec l'élément courant. Il est stable et a une complexité temporelle constante O(n²), indépendamment de l'ordre initial. Le code suivant modifie la logique de sélection :
def tri_selection(seq):
for i in range(len(seq) - 1):
indice_min = i
for j in range(i + 1, len(seq)):
if seq[j] < seq[indice_min]:
indice_min = j
if indice_min != i:
seq[i], seq[indice_min] = seq[indice_min], seq[i]
return seq
- Tri par tas
Utilisant un tas binaire (tas max ou min), ce tri construit initialement un tas max, puis extrait itérativement le maximum pour le placer à la fin. Il est instable mais offre une complexité temporlele constante O(n log n). Voici une version en Python avec des noms de fonctions et variables alternatifs :
def tri_par_tas(arr):
def ajuster(taille, racine):
max_idx = racine
gauche = 2 * racine + 1
droite = 2 * racine + 2
if gauche < taille and arr[gauche] > arr[max_idx]:
max_idx = gauche
if droite < taille and arr[droite] > arr[max_idx]:
max_idx = droite
if max_idx != racine:
arr[racine], arr[max_idx] = arr[max_idx], arr[racine]
ajuster(taille, max_idx)
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
ajuster(n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
ajuster(i, 0)
return arr
- Tri à bulles
Un tri simple qui compare et échange les éléments adjacents pour faire remonter les plus grands éléments. Il est stable avec une complexité spatiale O(1) et une complexité temporelle optimale O(n). L'exemple ci-dessous utilise une approche légèrement différente :
def tri_bulles(liste):
n = len(liste)
for i in range(n - 1):
permute = False
for j in range(0, n - i - 1):
if liste[j] > liste[j + 1]:
liste[j], liste[j + 1] = liste[j + 1], liste[j]
permute = True
if not permute:
break
return liste
- Tri rapide
Basé sur le principe diviser pour régner, ce tri choisit un pivot, partitionne la liste autour de celui-ci, et trie récursivement les sous-listes. Il est instable et a une complexité spatiale O(n log n) due à la pile de récursion. Une implémentation en Python avec des variables et logique modifiées :
def tri_rapide(seq, debut, fin):
if debut < fin:
pivot_idx = partitionner(seq, debut, fin)
tri_rapide(seq, debut, pivot_idx - 1)
tri_rapide(seq, pivot_idx + 1, fin)
return seq
def partitionner(arr, bas, haut):
pivot = arr[haut]
i = bas - 1
for j in range(bas, haut):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[haut] = arr[haut], arr[i + 1]
return i + 1
# Exemple d'appel
# liste = [3,6,8,10,1,2,1]
# tri_rapide(liste, 0, len(liste)-1)
- Tri par fusion
Ce tri divise la liste en sous-listes, les trie, puis les fusionne. Il est stable avec une complexité temporelle constante O(n log n) et nécessite une complexité spatiale O(n) pour stocker les sous-listes. L'implémentation suivante modifie la structure de fusion :
def tri_fusion(arr):
if len(arr) <= 1:
return arr
milieu = len(arr) // 2
gauche = tri_fusion(arr[:milieu])
droite = tri_fusion(arr[milieu:])
return fusionner(gauche, droite)
def fusionner(liste1, liste2):
resultat = []
i = j = 0
while i < len(liste1) and j < len(liste2):
if liste1[i] < liste2[j]:
resultat.append(liste1[i])
i += 1
else:
resultat.append(liste2[j])
j += 1
resultat.extend(liste1[i:])
resultat.extend(liste2[j:])
return resultat
- Tri par comptage
Un tri par compartiment qui utilise un tableau de comptage pour les valeurs, puis remplit la liste triée. Il est stable et a une complexité temporelle O(n + k) où k est la plage de valeurs. Le code ci-dessous change les noms de variables et la logique de remplissage :
def tri_comptage(seq):
if not seq:
return seq
min_val, max_val = min(seq), max(seq)
compteur = [0] * (max_val - min_val + 1)
for val in seq:
compteur[val - min_val] += 1
resultat = []
for idx, cnt in enumerate(compteur):
resultat.extend([idx + min_val] * cnt)
return resultat
- Tri par base
Ce tri trie les éléments par chiffres, des moins significatifs aux plus significatifs, en utilisant un tri stable à chaque étape. Il est stable et adapté aux entiers. Une implémentation Python avec des modifications de structure :
def tri_base(arr):
def tri_chiffre(seq, exp):
n = len(seq)
sortie = [0] * n
compteur = [0] * 10
for num in seq:
index = (num // exp) % 10
compteur[index] += 1
for i in range(1, 10):
compteur[i] += compteur[i - 1]
for i in range(n - 1, -1, -1):
index = (seq[i] // exp) % 10
sortie[compteur[index] - 1] = seq[i]
compteur[index] -= 1
for i in range(n):
seq[i] = sortie[i]
max_val = max(arr)
exp = 1
while max_val // exp > 0:
tri_chiffre(arr, exp)
exp *= 10
return arr