Tri de listes chaînées : algorithmes et implémentations en Python
Cet article présente plusieurs algorithmes de tri appliqués aux listes chaînées, avec leurs implémentations en Python. Chaque algorithme est accompagné de son analyse de complexité.
- Tri à bulles
En raison de l'accès séquentiel d'une liste chaînée, un pointeur de fin (queue) est nécessaire pour marquer la zone triée. La logique reste similaire au tri à bulles sur un tableau.
def tri_bulles(tete):
courant = tete
fin = None
while courant:
comparaison = tete
while comparaison and comparaison.suivant != fin:
if comparaison.val > comparaison.suivant.val:
comparaison.val, comparaison.suivant.val = comparaison.suivant.val, comparaison.val
comparaison = comparaison.suivant
fin = comparaison
courant = courant.suivant
return tete
Complexité temporelle : O(n²) | Complexité spatiale : O(1)
- Tri par sélection
On maintient un pointeur vers le nœud minimum dans la zone non triée. On parcourt la zone non triée et on échange si un nœud plus petit est trouvé.
def tri_selection(tete):
courant = tete
while courant and courant.suivant:
min_noeud = courant
explorateur = courant.suivant
while explorateur:
if explorateur.val < min_noeud.val:
min_noeud = explorateur
explorateur = explorateur.suivant
if courant != min_noeud:
courant.val, min_noeud.val = min_noeud.val, courant.val
courant = courant.suivant
return tete
Complexité temporelle : O(n²) | Complexité spatiale : O(1)
- Tri par insertion
On crée un nœud sentinelle (garde) pour faciliter l'insertion. On maintient un pointeur vers le dernier nœud de la partie triée.
def tri_insertion(tete):
if not tete or not tete.suivant:
return tete
garde = Noeud(-1)
garde.suivant = tete
dernier_trie = tete
courant = tete.suivant
while courant:
if dernier_trie.val <= courant.val:
dernier_trie = dernier_trie.suivant
else:
precedent = garde
while precedent.suivant.val <= courant.val:
precedent = precedent.suivant
dernier_trie.suivant = courant.suivant
courant.suivant = precedent.suivant
precedent.suivant = courant
courant = dernier_trie.suivant
return garde.suivant
Complexité temporelle : O(n²) | Complexité spatiale : O(1)
- Tri fusion
Étape de division : Utilisation de pointeurs rapide et lent pour trouver le milieu de la liste. La liste est coupée récursivement jusqu'à obtenir des listes d'un seul élément.
Étape de fusion : Fusion récursive des listes triées en comparant leurs éléments tête.
def fusionner(gauche, droite):
garde = Noeud(-1)
courant = garde
while gauche and droite:
if gauche.val < droite.val:
courant.suivant = gauche
gauche = gauche.suivant
else:
courant.suivant = droite
droite = droite.suivant
courant = courant.suivant
courant.suivant = gauche if gauche else droite
return garde.suivant
def tri_fusion(tete):
if not tete or not tete.suivant:
return tete
lent, rapide = tete, tete.suivant
while rapide and rapide.suivant:
lent = lent.suivant
rapide = rapide.suivant.suivant
milieu = lent.suivant
lent.suivant = None
gauche_triee = tri_fusion(tete)
droite_triee = tri_fusion(milieu)
return fusionner(gauche_triee, droite_triee)
Complexité temporelle : O(n log n) | Complexité spatiale : O(log n) pour la pile d'appels récursifs
- Tri rapide
Sélection d'un pivot (souvent le premier élément). Partitionnement de la liste autour du pivot en utilisant deux pointeurs pour séparer les éléments inférieurs et supérieurs.
def partitionner(debut, fin):
if debut == fin or debut.suivant == fin:
return debut
pivot_val = debut.val
inserer = debut
explorer = debut.suivant
while explorer != fin:
if explorer.val < pivot_val:
inserer = inserer.suivant
inserer.val, explorer.val = explorer.val, inserer.val
explorer = explorer.suivant
inserer.val, debut.val = debut.val, inserer.val
return inserer
def tri_rapide(debut, fin):
if debut == fin or debut.suivant == fin:
return debut
pivot = partitionner(debut, fin)
tri_rapide(debut, pivot)
tri_rapide(pivot.suivant, fin)
Complexité temporelle : O(n log n) en moyenne | Complexité spatiale : O(log n)
- Tri par comptgae
On détermine la plage des valeurs (min et max), on compte les occurrences de chaque valeur, puis on reconstruit la liste triée.
def tri_comptage(tete):
if not tete:
return tete
min_val = max_val = tete.val
courant = tete
while courant:
if courant.val < min_val: min_val = courant.val
if courant.val > max_val: max_val = courant.val
courant = courant.suivant
taille = max_val - min_val + 1
comptages = [0] * taille
courant = tete
while courant:
comptages[courant.val - min_val] += 1
courant = courant.suivant
garde = Noeud(-1)
courant = garde
for i in range(taille):
while comptages[i] > 0:
courant.suivant = Noeud(i + min_val)
courant = courant.suivant
comptages[i] -= 1
return garde.suivant
Complexité temporelle : O(n + k) | Complexité spatiale : O(k) où k est la plage des valeurs
- Tri par seaux (Bucket Sort)
Les éléments sont distribués dans des seaux (buckets) selon une règle de répartition. Chaque seau est trié individuellement, puis les seaux sont concaténés.
def tri_seaux(tete, taille_seau=5):
if not tete:
return tete
min_val = max_val = tete.val
courant = tete
while courant:
if courant.val < min_val: min_val = courant.val
if courant.val > max_val: max_val = courant.val
courant = courant.suivant
nb_seaux = (max_val - min_val) // taille_seau + 1
seaux = [[] for _ in range(nb_seaux)]
courant = tete
while courant:
indice = (courant.val - min_val) // taille_seau
seaux[indice].append(courant.val)
courant = courant.suivant
garde = Noeud(-1)
courant = garde
for seau in seaux:
seau.sort()
for valeur in seau:
courant.suivant = Noeud(valeur)
courant = courant.suivant
return garde.suivant
Complexité temporelle : O(n + m log m) en moyenne | Complexité spatiale : O(n + m) où m est le nombre de seaux
- Tri par base (Radix Sort)
Les éléments sont triés chiffre par chiffre, des moins significatifs aux plus significatifs, en utilisant un tri stable à chaque passage.
def tri_base(tete):
def obtenir_longueur_max(liste):
longueur = 0
courant = liste
while courant:
longueur = max(longueur, len(str(courant.val)))
courant = courant.suivant
return longueur
def obtenir_chiffre(nombre, position):
return (nombre // (10 ** position)) % 10
longueur_max = obtenir_longueur_max(tete)
for position in range(longueur_max):
seaux = [[] for _ in range(10)]
courant = tete
while courant:
chiffre = obtenir_chiffre(courant.val, position)
seaux[chiffre].append(courant.val)
courant = courant.suivant
garde = Noeud(-1)
courant = garde
for seau in seaux:
for valeur in seau:
courant.suivant = Noeud(valeur)
courant = courant.suivant
tete = garde.suivant
return tete
Complxeité temporelle : O(n * d) | Complexité spatiale : O(n + 10)
Remarques importantes :
- Le tri de Shell n'est pas adapté aux listes chaînées en raison de l'accès aléatoire nécessaire.
- Le tri par tas est plus naturel sur les structures de données à accès séquentiel comme les tableaux.
- Pour les listes chaînées, les algorithmes les plus importants à maîtriser sont le tri par insertion et le tri fusion.