Algorithme de tri fusion

Cours/Algorithmie/Problème du tri/Algorithme de tri fusion

Le tri fusion est un tri de complexité optimale : $\mathcal{O}(n\ln(n))$ opérations où $n$ est la taille de la liste en entrée. Il fonctionne selon principe algorithme de diviser pour régner :

À retenir

Un algorithme de la forme diviser pour régner fonctionne en deux parties :

résoudre $k$ sous-problèmes du problème initial
combiner les $k$ solutions des sous-problèmes en une solution du problème initial

Puisqu'il suffit de s'utiliser lui pour résoudre les sous-problèmes sa forme générale est :

algorithme algo(données):
    A partir de données créer k données_partielles_i (1 ≤ i ≤ k)
    pour chaque i  de [1, k]:
        solution_i = algo(données_partielles_i)

    solution = combiner(solution_1, ..., solution_k)

    rendre solution

L'intérêt de ces programme est que si la complexité de la fonction combiner est faible, la complexité de l'algorithme l'est également.

Combiner

Pour un tri, si on scinde le tableau le tableau en tableau plus petit que l'on tri, le but de la fonction combiner est de créer un tableau trié à partir de tableaux triés.

L'algorithme ci-après le fait de façon optimale, en $\mathcal{O}(\vert T1 \vert + \vert T2 \vert)$ :

algorithme combiner(T1: [entier], T2: [entier]) → [entier]:
    i1 ← 0
    i2 ← 0
    T ← un tableau de taille T1.longueur + T2.longueur
    tant que i1+i2 < T.longueur:
        si i2 == T2.longueur:
            T[i1 + i2] ← T1[i1]
            i1 ← i1 + 1
        sinon si i1 == T1.longueur:
            T[i1 + i2] ← T2[i2]
            i2 ← i2 + 1
        sinon si T1[i1] < T2[i2]:
            T[i1 + i2] ← T1[i1]
            i1 ← i1 + 1
        sinon:
            T[i1 + i2] ← T2[i2]
            i2 ← i2 + 1
    rendre T

Faites attentions aux raccourcis que l'on serait tenté de faire en ne regardant que rapidement le code :

Montrer que l'algorithme combiner précédent n'est pas équivalent à celui-ci :

algorithme combiner_faux(T1: [entier], T2: [entier]) → [entier]:
    i1 ← 0
    i2 ← 0
    T ← un tableau de taille T1.longueur + T2.longueur
    tant que i1+i2 < T.longueur:
        si (i2 == T2.longueur) OU (T1[i1] < T2[i2]):
            T[i1 + i2] ← T1[i1]
            i1 ← i1 + 1
        sinon:
            T[i1 + i2] ← T2[i2]
            i2 ← i2 + 1

    rendre T

corrigé

Si i2 < T2.longueur mais que i1 = T1.longueur l'algorithme va planter car il va tenter d'accéder à T1[i1] qui n'existe pas.

Faites très attention aux conditions. C'est très souvent source d'erreurs quand on va trop vite...

Fonctionnement

On vérifie pour deux petits tableaux triés. Par exemple pour T1=[1, 4, 7] et T2=[0, 2, 3, 98]. T vaudra :

[0] après la 1ère itération (i1=0 et i2=1)
[0, 1] après la 2nde itération (i1=1 et i2=1)
[0, 1, 2] après la 3ème itération (i1=1 et i2=2)
[0, 1, 2, 3] après la 4ème itération (i1=1 et i2=3)
[0, 1, 2, 3, 4] après la 5ème itération (i1=2 et i2=3)
[0, 1, 2, 3, 4, 7] après la 6ème itération (i1=3 et i2=3)
[0, 1, 2, 3, 4, 7, 98] après la 7ème itération (i1=3 et i2=4)

Preuve

L'algorithme se finit bien puisqu'à chaque itération de la boucle while soit i1 soit i2 augmente. Au bout de T1.longueur + T2.longueur itérations on aura i1 = T1.longueur et i2 = T2.longueur, donc la condition de la boucle tant que ne sera plus vérifiée.

L'invariant de boucle que l'on peut facilement prouver est :

Invariant de boucle

À la fin de chaque itération, T[:i1 + i2] est trié et contient les i1 premiers éléments de T1 et les i2 premiers éléments de T2

Complexités

Allons un peu plus vite :

on a une boucle tant que de T1.longueur + T2.longueur itérations
chaque ligne de l'algorithme est en $\mathcal{O}(1)$

Proposition

La complexité max et min de combiner est $\mathcal{O}(n_1 + n_2)$ avec $n_1$ et $n_2$ les tailles des tableaux T1 et T2 respectivement.

Pseudo-code

Avec notre fonction combiner(T1, T2) le pseudo code de l'algorithme fusion est :

algorithme fusion(T: [entier]) → [entier]:
    si T.longueur < 2:
        rendre T
    sinon:
        milieu = T.longueur // 2
        T1 ← nouveau tableau contenant T[:milieu]
        T2 ← nouveau tableau contenant T[milieu:]

        T1_trié ← fusion(T1)
        T2_trié ← fusion(T2)
        T_trié ← combiner(T1_trié, T2_trié)

        rendre T_trié

Preuve

Comme milieu < T.longueur si T.longueur > 1, l'algorithme va bien converger et s'arrêter. De plus, comme l'algorithme combiner est démontré, fusion est bien un algorithme de tri.

Complexités

La complexité de l'algorithme fusion est (avec $n$ la taille du tableau passé en entrée) :

$$C(n) = 2 \cdot C(\frac{n}{2}) + D(n)$$

Où :

$C(n)$ est la complexité de l'algorithme fusion pour une liste à $n$ éléments (algorithme fusion)
$D(n)$ est la complexité de fusionner deux listes triées en une unique liste triées (algorithme combiner).

Comme l'algorithme combiner est en $\mathcal{O}(n)$, l'équation de récurrence de la complexité est :

$$ C(n) = 2 \cdot C(\frac{n}{2}) + \mathcal{O}(n) $$

Pour connaître la valeur de la complexité on peut utiliser le master theorem qui est LE théorème des complexités pour les algorithmes récursifs (on le verra lorsque l'on étudiera en détail les algorithmes de type diviser pour régner). Mais ici pas besoin d'invoquer l'artillerie lourde, on peut aisément calculer la complexité à la main :

Proposition

La complexité de l'algorithme fusion est $\mathcal{O}(n\ln(n))$ où $n$ est la taille de la liste en entrée

preuve

$$ \begin{array}{lcl} C(n) &=& 2 \cdot C(\frac{n}{2}) + \mathcal{O}(n)\\ &=& 2 \cdot (2 \cdot (C(\frac{n}{4}) + \mathcal{O}(\frac{n}{2})) + \mathcal{O}(n)\\ &=& 2^2 \cdot C(\frac{n}{2^2}) + 2 \cdot \mathcal{O}(\frac{n}{2}) + \mathcal{O}(n)\\ &=& 2^2 \cdot C(\frac{n}{2^2}) + 2 \cdot \mathcal{O}(n)\\ &=& ...\\ &=& 2^i \cdot C(\frac{n}{2^i}) + k \cdot \mathcal{O}(n)\\ &=& ...\\ &=& 2^{\log_2(n)} \cdot C(1) + \log_2(n) \cdot \mathcal{O}(n)\\ &=& n \cdot C(1) + \log_2(n) \cdot \mathcal{O}(n)\\ &=& \mathcal{O}(n) + \log_2(n) \cdot \mathcal{O}(n)\\ &=& \mathcal{O}(n\log_2(n))\\ &=& \mathcal{O}(n\ln(n)) \end{array} $$

Tout comme le tri par sélection, le tri fusion a la particularité d'avoir toujours le même nombre d'opérations quelque soit la liste en entrée. Attention cependant, le tri fusion n'est pas in place, il rend un nouveau tableau.