forked from menault/TD4_DEV51_Qualite_Algo
29 lines
1.2 KiB
Python
29 lines
1.2 KiB
Python
def entree_tri_fusion_multi(tab):
|
|
tab = [tri_fusion(sub_tab) for sub_tab in tab] # Appliquer le tri fusion à chaque sous-tableau
|
|
return sorted(tab, key=sum) # Trier les sous-tableaux par la somme de leurs éléments
|
|
|
|
def tri_fusion(tab):
|
|
if len(tab) <= 2:
|
|
if tab[0] > tab[-1]:
|
|
return tab[::-1]
|
|
return tab
|
|
mid = len(tab) // 2 # Trouver le milieu du tableau
|
|
left = tri_fusion(tab[:mid]) # Diviser et trier la moitié gauche
|
|
right = tri_fusion(tab[mid:]) # Diviser et trier la moitié droite
|
|
return fusion(left, right) # Fusionner les deux moitiés triées
|
|
|
|
def fusion(left, right):
|
|
result = []
|
|
i = j = 0
|
|
while i < len(left) and j < len(right): # Tant qu'il reste des éléments dans les deux sous-tableaux
|
|
if left[i] < right[j]: # Comparer les éléments des deux sous-tableaux
|
|
result.append(left[i]) # Ajouter l'élément de gauche s'il est plus petit
|
|
i += 1
|
|
else:
|
|
result.append(right[j]) # Ajouter l'élément de droite sinon
|
|
j += 1
|
|
result.extend(left[i:]) # Ajouter les éléments restants de gauche
|
|
result.extend(right[j:]) # Ajouter les éléments restants de droite
|
|
return result
|
|
|