Comment on fait un tri fusion en python
- User
Comment on fait un tri fusion en python
Assistant
Le tri fusion (ou merge sort en anglais) est un algorithme de tri efficace basé sur le paradigme "diviser pour régner". Il consiste à diviser la liste en deux moitiés, trier chaque moitié récursivement, puis fusionner les deux listes triées.
Voici comment implémenter le tri fusion en Python :
✅ Implémentation simple du tri fusion
def tri_fusion(liste): # Cas de base : si la liste a 0 ou 1 élément, elle est déjà triée if len(liste) <= 1: return liste # Diviser la liste en deux milieu = len(liste) // 2 gauche = tri_fusion(liste[:milieu]) droite = tri_fusion(liste[milieu:]) # Fusionner les deux moitiés triées return fusion(gauche, droite) def fusion(gauche, droite): resultat = [] i = j = 0 # Comparer les éléments et les ajouter dans l'ordre while i < len(gauche) and j < len(droite): if gauche[i] < droite[j]: resultat.append(gauche[i]) i += 1 else: resultat.append(droite[j]) j += 1 # Ajouter les éventuels éléments restants resultat.extend(gauche[i:]) resultat.extend(droite[j:]) return resultat
🧪 Exemple d'utilisation
ma_liste = [5, 2, 8, 3, 1, 7, 4] print("Avant tri :", ma_liste) ma_liste_triee = tri_fusion(ma_liste) print("Après tri :", ma_liste_triee)Sortie :
Avant tri : [5, 2, 8, 3, 1, 7, 4] Après tri : [1, 2, 3, 4, 5, 7, 8]
🔍 Explication rapide
- Diviser : on coupe la liste en deux.
- Régner : on trie chaque moitié récursivement.
- Combiner : on fusionne les deux listes triées en une seule.
La complexité temporelle est de O(n log n) dans tous les cas, ce qui le rend très efficace pour les grandes listes.
Tu veux que je t’explique aussi comment modifier cette fonction pour qu’elle trie des objets personnalisés ou des tuples ?
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.