Tri fusion

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Tri fusion

Suit diviser pour mieux régner
- Diviser
  - divise le problème en sous-problèmes
- Mieux régner
  - sous-problèmes résolus récursivement
- Combiner
  - solutions des sous-problèmes combinées pour obtenir solution finale

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. La liste a été divisée en deux parties.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. La liste a été divisée en deux parties. Il y a deux nouvelles listes, la première contient la moitié gauche de la liste d’origine et la seconde la moitié droite de la liste d’origine.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les nouvelles listes ont été divisées en deux parties.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Il existe de nouvelles listes avec les divisions des dernières listes divisées.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les nouvelles listes ont été divisées en deux parties.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Il existe de nouvelles listes avec les divisions des dernières listes divisées.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les nouvelles listes ont été divisées en deux parties.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les nouvelles listes ont été divisées en deux parties.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les éléments des dernières listes divisées ont été triés.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les éléments des dernières listes divisées ont été fusionnés et ordonnés.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les éléments des dernières listes divisées ont été fusionnés et ordonnés.

Tri fusion - en action

Une représentation schématique d’une liste avec des nombres non ordonnés. Les éléments des dernières listes divisées ont été fusionnés et ordonnés. Tous les éléments sont triés.

Tri fusion - implémentation

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

Tri fusion - complexité

Pire cas : $O(n\log{}n)$
- amélioration par rapport tri à bulles, tri par sélection et tri par insertion
- adapté au tri de grandes listes
Cas moyen : $\Theta(n\log{}n)$
Meilleur cas : $\Omega(n\log{}n)$
- autres algorithmes (tri bulles/par insertion) ont meilleure complexité dans meilleur cas
Complexité spatiale : $O(n)$
- pire complexité spatiale qu'autres algorithmes avec $O(1)$
D’autres variantes réduisent complexité spatiale

Passons à la pratique !

Structures de données et algorithmes en Python