C11.3 : Tri fusion

L'algorithme du tri fusion a été inventé par le mathématicien américain John von Neumann dans les années 1940. Cependant, le tri fusion a été popularisé par le livre "The Art of Computer Programming" de Donald Knuth (publié en 1968), qui a contribué à sa reconnaissance en tant qu'algorithme de tri efficace et pratique.

Principe d'un algorithme "diviser pour régner"

En informatique, "diviser pour régner" est une technique algorithmique consistant à :

  • • Diviser : découper un problème initial en sous-problèmes ;
  • • Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
  • • Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.

Application au tri-fusion

Présentation de la méthode

Le tri fusion est une méthode de tri utilisant un algorithme "diviser pour régner".

C'est une méthode de tri efficace.

Les étapes de l'algorithme consistent à :

Mise en œuvre

Fonction coupe(L)

Écrire une fonction qui prend une liste en paramètre et sépare ses éléments en deux listes (de tailles identiques à 1 près) qu'elle renvoie.

Fonction fusion(L1, L2)

Écrire une fonction qui prend deux listes triées en paramètres et renvoie une liste triée correspondant à la fusion de ces deux listes.

Fonction récursive tri_fusion(L)

Écrire une fonction récursive qui prend une liste en paramètre et renvoie une liste triée.

Afficher la correction 
def fusion(L1, L2):
    # fusion de deux listes triées
    liste = []
    pos1 = 0
    pos2 = 0
    while pos1 < len(L1) or pos2 < len(L2):
        if pos1 >= len(L1):
            liste = liste + [L2[pos2]]
            pos2 += 1
        elif pos2 >= len(L2):
            liste = liste + [L1[pos1]]
            pos1 += 1
        else:
            if L1[pos1] < L2[pos2]:
                liste = liste + [L1[pos1]]
                pos1 += 1
            else:
                liste = liste + [L2[pos2]]
                pos2 += 1
    return liste

def coupe_v1(L):
    m = len(L) // 2
    return L[0:m], L[m:]

def coupe_v2(L):
    L1 = []
    L2 = []
    pos = 0
    while pos < len(L):
        L1 = L1 + [L[pos]]
        L1, L2 = L2, L1
        pos = pos +1
    return L1, L2

def tri_fusion(L):
    if len(L) <= 1:
        L_triee = L
    else:
        # Diviser
        L1, L2 = coupe_v2(L)
        # Régner
        L1_triee = tri_fusion(L1)
        L2_triee = tri_fusion(L2)
        # Combiner
        L_triee = fusion(L1_triee, L2_triee)
    return L_triee

def tri_fusion_version_condensee(L):
    if len(L) <= 1:
        return L1
    else:
        L1, L2 = coupe_v2(L)
        return fusion(tri_fusion_version_condensee(L1), tri_fusion_version_condensee(L2))

liste = [10,9,8,7,6,5,4]
print(tri_fusion(liste))

Efficacité du tri fusion

Écrire un programme qui compare l'efficacité du tri par insertion, du tri par sélection et du tri fusion.

Pour cela on écrira un programme qui trace les courbes donnant le temps de tri de chacun de ces trois algorithmes en fonction du nombre d'éléments à trier.

Afficher la correction 
from time import perf_counter
from random import randint
import matplotlib.pyplot as plt

# =========================
# ===== Tri insertion =====

def tri_insertion(L):
    liste = list(L)
    for i in range(1, len(liste)):
        j = i
        elt = liste[i]
        while elt < liste[j-1] and j > 0:
            liste[j] = liste[j-1]
            j = j - 1
        liste[j] = elt
    return liste

# =========================
# ===== Tri selection =====

def tri_selection(L):
    liste = list(L)
    for i in range(0, len(liste)-1):
        for j in range(i+1, len(liste)):
            if liste[j] < liste[i]:
                liste[i], liste[j] = liste[j], liste[i]
    return liste

def tri_selection_v2(L):
    liste = list(L)
    for i in range(0, len(liste)-1):
        mini = liste[i]
        for j in range(i+1, len(liste)):
            if liste[j] < mini:
                mini, liste[j] = liste[j], mini
        liste[i] = mini
    return liste

# ======================
# ===== Tri fusion =====

def fusion(L1, L2):
    # fusion de deux listes triées
    liste = []
    pos1 = 0
    pos2 = 0
    while pos1 < len(L1) or pos2 < len(L2):
        if pos1 >= len(L1):
            liste.append(L2[pos2])
            pos2 += 1
        elif pos2 >= len(L2):
            liste.append(L1[pos1])
            pos1 += 1
        else:
            if L1[pos1] < L2[pos2]:
                liste.append(L1[pos1])
                pos1 += 1
            else:
                liste.append(L2[pos2])
                pos2 += 1
    return liste

def coupe(L):
    m = len(L)//2
    return L[0:m], L[m:]

def tri_fusion(L):
    if len(L) <= 1:
        return L
    else:
        L1, L2 = coupe(L)
        return fusion(tri_fusion(L1),tri_fusion(L2))

# ===========================================
# ===== Affichage sous forme de courbes =====

def liste_y(fct, liste_x):
    liste = []
    for x in liste_x:
        liste_a_trier = [randint(0,999) for _ in range(x)]
        t0 = perf_counter()
        fct(liste_a_trier)
        t1 = perf_counter()
        liste.append((t1-t0)*1000)
    return liste

liste_x = list(range(1,1000,10))

plt.plot(liste_x,liste_y(tri_insertion, liste_x), label='tri insertion')
plt.plot(liste_x,liste_y(tri_selection, liste_x), label='tri selection')
plt.plot(liste_x,liste_y(tri_fusion, liste_x), label='tri fusion')

plt.legend()

plt.show()