video d'introduction sur le tri par fusion

Le tri fusion

Description du tri

Dans cette partie, nous allons essayer de comprendre les principes sur lesquels s’appuie ce tri. Son implémentation, pour des tableaux ou des listes chaînées, sera développée dans les prochaines sections.

Le tri fusion s’appuie sur la méthode Diviser pour régner pour trier les n éléments d’une séquence S :

1. Diviser : Si la séquence S est composée de 0 ou un élément, retourner S immédiatement ; cette séquence est déjà triée. Si la séquence S est composée de plus de deux éléments, la diviser en deux sous-séquences S_1 et S_2 contenant chacune environ la moitié des éléments de S ; donc S_1 est formée des n/2 premiers éléments de S contient les n/2 derniers éléments de S.

2. Régner : Trier récursivement S_1 et S_2.

3. Combiner : Reformer la séquence S en combinant, dans l’ordre, les éléments des séquences triées S_1 et S_2.

Pour bien comprendre la méthode employée, le plus simple est de construire un arbre binaire dans lequel chaque nœud est le résultat d’un appel récursif.

Résultats des différents appels récursifs (Partie Diviser).

Résultats progressifs après les étapes Régner et Fusionner.

Décomposition de l’exécution de l’algorithme

Légende

• Chaque nœud représente un appel récursif ;
• Nœud avec une bordure en pointilles : appels récursifs non encore effectués ;
• Nœud avec une bordure en gras : appel récursif en cours ;
• Nœud vide avec une bordure : partie déjà traitée ;
• Nœud en partie vide (contenant tout de même des valeurs) : appels récursifs en attente.

Implémentation du tri fusion pour un tableau

1. Étudier le code suivant et expliquer comment s’effectue la fusion.

def fusion(S1: List[int], S2: List[int], S: List[int]) -> None:
"""
Combine les éléments des deux listes S1 et S2 dans la liste S (en place).
 i est le nombre d'élément(s) de S1 copié(s) dans S1. 
j est le nombre d'élément(s) de S2 copié(s) dans S2. 
On doit donc avoir i + j <= len(S).
 """
i = 0
j = 0
                            
while i + j < len(S):
    if j == len(S2) or (i < len(S1) and S1[i] < S2[j]):
        S[i + j] = S1[i]
        i = i + 1
    else:
        S[i + j] = S2[j]
        j = j + 1

2. Étudier le code suivant et remplacer les … pour chaque numéro.

def tri_fusion(S: List[int]) -> None:
"""
Implémentation du tri fusion.
La liste S est modifiée en place.
"""
n = len(S)  # ... (0)

if n < 2:
    return None  # ... (1)

# Diviser, Régner, Combiner ? ... (2)
milieu = n // 2
S1 = S[:milieu]  # .... (3)
S2 = S[milieu:]  # .... (4)
                            
# Diviser, Régner, Combiner ? ... (5)
tri_fusion(S1)  # ... (6)
tri_fusion(S2)  # ... (7)
          
# Diviser, Régner, Combiner ? ... (8)
fusion(S1, S2, S)  # ... (9)
                            

3. Étudier le comportement du programme complet à l’aide de pythontutor.
   Construire la liste à l’aide de l’instruction :

liste = [randint(1, 400) for i in range(5)]
                            

4. autre manière de coder peut être plus expressive: testez-le

   def tri_fusion(tableau):
       if  len(tableau) <= 1: 
           return tableau
       pivot = len(tableau)//2
       tableau1 = tableau[:pivot]
       tableau2 = tableau[pivot:]
       gauche = tri_fusion(tableau1)
       droite = tri_fusion(tableau2)
       fusionne = fusion(gauche,droite)
       return fusionne
   #Tri fusion fonction de fusion de 2 listes
   def fusion(tableau1,tableau2):
       indice_tableau1 = 0
       indice_tableau2 = 0    
       taille_tableau1 = len(tableau1)
       taille_tableau2 = len(tableau2)
       tableau_fusionne = []
       while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
           if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
               tableau_fusionne.append(tableau1[indice_tableau1])
               indice_tableau1 += 1
           else:
               tableau_fusionne.append(tableau2[indice_tableau2])
               indice_tableau2 += 1
       while indice_tableau1<taille_tableau1:
           tableau_fusionne.append(tableau1[indice_tableau1])
           indice_tableau1+=1
       while indice_tableau2<taille_tableau2:
           tableau_fusionne.append(tableau2[indice_tableau2])
           indice_tableau2+=1
       return tableau_fusionne

5. Quelle est la complexité de la fonction fusion ?

6. Essayer d’évaluer la complexité de l’algorithme sans faire de calcul.

7. Evaluer la complexité en temps avec time en utilisant le code suivant

   import time
   import numpy
                      
   def temps(N):
       n = 100
       t1 = time.clock()
       for k in range(n):
           liste = numpy.random.randint(0,N,size=N)
           tri_fusion(liste)
       t1 = time.clock()-t1

   comparer avec les deux tris que vous connaissez (selection et insertion) en modifiant la valeur de N. Vous pouvez "retourner" le quotient des temps

8. Pour les plus rapides, vous pouvez coder le tri par fusion de manière itérative

voici une illustration visuelle de la méthode divide and conquer.