Le tri fusion est un tri efficace et stable qui applique le principe “diviser pour règner”. Il consiste à découper le tableau en deux, à trier chaque sous-partie, puis à fusionner. C’est un algorithme récursif. Exemple :
| indices | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| valeurs | 3 | 6 | 1 | 5 | 2 | 2 | 4 |
Au premier appel, on découpe le tableau en deux (partage au milieu, soit au niveau de l’indice 3, on on rappèle la fonction entre les indices 0 à 3 et 4 à 6, ce qui permettra d’obtenir deux sous-tableaux triés :
| indices | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| valeurs | 1 | 3 | 6 | 2 | 2 | 4 | 5 |
Il reste à fusionner les sous-parties [1, 3, 6] et [2, 2, 4, 5].
La récursion s’arrête (cas de base) quand la taille du sous-tableau est inférieure à 2.
Opération de fusion
Plusieurs algorithmes sont possibles pour cette opération, à sélectioner selon le compromis temps-mémoire.
L’algorithme utilise trois tableaux tab, left et right, les deux derniers
étant des sous-tableaux du premier (copies - ce qui à un coup mémoire) :
tab=[1, 3, 6, 2, 2, 4, 5],iest l’indice du prochain élément à écraser ;left=[1, 3, 6];iLeftest l’indice du prochain élément de ce tableau à insérer ;et
right=[2, 2, 4, 5], avec l’indiceiRight.A la première itération,
iRightet iLeft valent 0, et l’algorithme compareleft[iLeft](1) àright[iRight](2), et place le plus petit (1) puis incrémente l’indice correspondant (iciiLeft).
A la deuxième itération, iLeft vaut 1 et left[iLeft] vaut 3. Par conséquent
la valeur à placer est 2, et cette fois c’est iRight qui est incrémenté :
| indices | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| valeurs | 1 | 2 | / | / | / | / | / |
Et ainsi de suite.
La complexité en temps de calcul de cet algorithme est en O(n.log2(n)) :
le tableau est divisé en 2 log2(n) fois, et à chaque niveau de récursion,
ce sont n éléments qui sont fusionnées.
Pour des raisons de simplicité et de qualité, ces fonctions sont séparées de l’algorithme de tri.
from typing import List
import math #pour le calcul de la complexité théorique
def fusionCopie(tab : List[int], inf : int, sup : int) -> List[int]:
"""
@param tab le tableau à fusionner, en entrée-sortie
@param inf la borne inférieure de la zone à fusionner
@param inf la borne supérieure de la zone à fusionner
prérequis: le calcul du milieu (séparation gauche-droite) doit être le
même que dans la fonction appelante: mid = inf + (sup - inf) // 2
@return le tableau fusionné (pour doctests)
>>> fusionCopie([1, 5, 9, 2, 3, 4, 5], 0, 7)
[1, 2, 3, 4, 5, 5, 9]
"""
global cout #CPLX
mid = inf + (sup - inf) // 2
left = tab[inf:mid] #copie (coût mémoire)
iLeft = 0
right = tab[mid:sup]
iRight = 0
for i in range(inf, sup): #fusion entre inf et sup
cout += 1 #CPLX
if iLeft != len(left) and (iRight == len(right) or left[iLeft] < right[iRight]):
tab[i] = left[iLeft]
iLeft += 1
else:
tab[i] = right[iRight]
iRight += 1
return tab
Autre algorithme, avec tri en place — sans copie (mémoire), mais avec possible décalage d’éléments pour l’insertion :
def fusionEnPlace(tab : List[int], inf : int, sup : int) -> List[int]:
"""
@param tab le tableau à fusionner, en entrée-sortie
@param inf la borne inférieure de la zone à fusionner
@param inf la borne supérieure de la zone à fusionner
prérequis: le calcul du milieu (séparation gauche-droite) doit être le
même que dans la fonction appelante: mid = inf + (sup - inf) // 2
@return le tableau fusionné (pour doctests)
>>> fusionEnPlace([], 0, 0)
[]
>>> fusionEnPlace([1], 0, 1)
[1]
>>> fusionEnPlace([2, 1], 0, 2)
[1, 2]
>>> fusionEnPlace([0, 2, 1, 0], 1, 3)
[0, 1, 2, 0]
>>> fusionEnPlace([1, 0, 3, 2], 2, 4)
[1, 0, 2, 3]
>>> fusionEnPlace([0, 2, 1, 3], 0, 4)
[0, 1, 2, 3]
>>> fusionEnPlace([1, 5, 9, 2, 3, 4, 5], 0, 7)
[1, 2, 3, 4, 5, 5, 9]
"""
global cout #CPLX
mid = inf + (sup - inf) // 2
while inf != mid and mid != sup: #tant qu'une comparaison est possible (0(n))
cout += 1 #CPLX
if tab[inf] > tab[mid]:
tmp = tab[mid]
for k in range(mid, inf, -1): #décalage (coûteux en temps)
cout += 1 #CPLX
tab[k] = tab[k-1]
tab[inf] = tmp #insertion
mid += 1 #la partie gauche est agrandie
inf += 1
return tab
Remarque : il est inutile de renvoyer le tableau (car il est modifié par la fonction — cf passage en entrée-sortie), mais c’est plus pratique pour écrire des doctests.
Cette fonction sert d’enveloppe pour initialiser la sous-fonction récursive.
def triFusionRec(tab : List[int]) -> List[int]:
"""
trie le tableau selon la méthode du tri fusion, par ordre croissant
version récursive
@param tab le tableau de valeurs, en entrée-sortie (par adresse)
@return le tableau trié par ordre croissant (pour doctests)
>>> triFusionRec([])
[]
>>> triFusionRec([1])
[1]
>>> triFusionRec([2, 1])
[1, 2]
>>> triFusionRec([1, 3, 2])
[1, 2, 3]
>>> triFusionRec([4, 1, 3, 2])
[1, 2, 3, 4]
>>> triFusionRec([4, 2, 4, 2, 1, 4, 4])
[1, 2, 2, 4, 4, 4, 4]
"""
def triFusionRec_(tab : List[int], inf : int, sup : int):
mid = inf + (sup - inf) // 2
if inf + 1 != mid: #au moins 2 éléments à gauche
triFusionRec_(tab, inf, mid)
if mid + 1 != sup: #au moins 2 éléments à droite
triFusionRec_(tab, mid, sup)
# ~ fusionEnPlace(tab, inf, sup) #essayer l'une
fusionCopie(tab, inf, sup) #ou l'autre version
global cout #CPLX
cout = 0 #CPLX
if len(tab) > 1:
triFusionRec_(tab, 0, len(tab))
return tab
if __name__ == "__main__":
cout = 0; import doctest; doctest.testmod()
t1 = [1,3,9,5,8,4,7,2,6]
triFusionRec(t1)
print(t1)
n = len(t1)
print("complexité théorique : " + str(int(n*math.log2(n))))
print("complexité effective : " + str(cout))
Cette version utilise une pile LIFO
implémentée par tableau (List).
def triFusionIte(tab : List[int]) -> List[int]:
"""
trie le tableau selon la méthode du tri fusion, par ordre croissant
version itérative (récursion non terminale → requiert l'utilisation d'une pile)
@param tab le tableau de valeurs, en entrée-sortie (par adresse)
@return le tableau trié par ordre croissant (pour doctests)
>>> triFusionIte([])
[]
>>> triFusionIte([1])
[1]
>>> triFusionIte([2, 1])
[1, 2]
>>> triFusionIte([1, 3, 2])
[1, 2, 3]
>>> triFusionIte([4, 1, 3, 2])
[1, 2, 3, 4]
>>> triFusionIte([4, 2, 4, 2, 1, 4, 4])
[1, 2, 2, 4, 4, 4, 4]
"""
global cout #CPLX
cout = 0 #CPLX
p = []
if len(tab) > 1:
p.append(("T", 0, len(tab)))
while len(p) != 0:
action, inf, sup = p.pop()
if action == "T":
p.append(("F", inf, sup))
mid = inf + (sup - inf) // 2
if inf + 1 != mid: #au moins 2 éléments à gauche
p.append(("T", inf, mid))
if mid + 1 != sup: #au moins 2 éléments à droite
p.append(("T", mid, sup))
else: #action == "F"
fusionEnPlace(tab, inf, sup)
return tab