00:00 | 0 |
Le tri fusion est un autre algorithme de tri. Celui-ci présente l’avantage d’utiliser la méthode Diviser pour Regner.
Les étapes 1 et 2 de la méthode Diviser pour Regner consistent à diviser la liste en 2 sous-listes, de manière recursive, jusqu’à obtenir des listes de 1 élément.
Le tri fusion est réalisé par la fonction fusion suivante:
def fusion(L):
if len(L) <=1:
return L
m = len(L)//2
gauche = fusion(L[:m])
droite = fusion(L[m:])
return interclassement(gauche,droite)
L’étape 3, enfin consiste à interclasser les sous-listes deux à deux. Compléter le code de la fonction interclassement