Remarque
Le principe de l’algorithme de diviser pour régner consiste à découper un gros problème, difficile à résoudre, en petits problèmes plus simples.
Obtenir de petits problèmes
Résoudre les petits problèmes: une liste d’un élément est triée.
Trier
Et remonter
def tri_fusion(tab: list, deb: int, fin: int) -> None:
if deb < fin:
milieu = (deb+fin)//2
tri_fusion(tab, deb, milieu)
tri_fusion(tab, milieu+1, fin)
fusionner(tab, deb, fin)
def fusionner(tab: list, deb: int, fin: int) -> None:
res = []
milieu = (deb+fin)//2
i = deb
j = milieu+1
while i <= milieu and j <= fin:
if tab[i] < tab[j]:
res.append(tab[i])
i += 1
else:
res.append(tab[j])
j += 1
# ajout fin de tab
for i1 in range(i, milieu+1):
res.append(tab[i1])
for j1 in range(j, fin+1):
res.append(tab[j1])
# remplacement tab par res
for k in range(fin-deb+1):
tab[deb+k] = res[k]
- La complexité du découpage en sous-listes (fonction tri_fusion) est logarithmique.
- La complexité de la fusion (fonction fusionner) est linéaire.
À retenir
L’algorithme de tri fusion a une complexité: n*log2(n)