Chapitre 3: Diviser pour régner

Complexité des algorithmes de tri

En première, nous avons vu deux algorithmes peu performants:

• le tri par sélection qui a une complexité quadratique dans le pire des cas, le meilleur des cas et en moyenne.
• le tri par insertion qui a une complexité linéaire dans le meilleur des cas, et quadratique dans le pire des cas et en moyenne.

Ces algorithmes ne sont pas utilisés en pratique car peu efficaces. En effet, il a été prouvé que dans le pire des cas et en moyenne, on pouvait au mieux obtenir une complexité $O(n \log(n)$.

Cela fait une grande différence car $\log(n) \lll n$, en effet:

• $\log(n) = 10$ pour $n = 2^{10} = 1024$
• $\log(n) = 100$ pour $n = 2^{100} = 1267650600228229401496703205376$

On avait déjà rencontré ce type d'améliorations entre la recherche en table et la recherche dichotomique qui utilisait le principe «Diviser pour régner».

Le principe de diviser pour régner

Le principe de diviser pour régner consiste à ramener la résolution d'un problème sur N données à la résolution d'un problème sur la moitié des données et poursuivre ce découpage jusqu'à ce que le problème devienne évident(par exemple trier un tableau d'une donnée). Une fois que les solutions des sous problèmes ont été trouvées, on les combine pour obtenir la solution du problème complet.

• 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.

Article Wikipedia Diviser pour régner

Image par Fschwarzentruber — Travail personnel, CC BY-SA 4.0, Lien

Le tri fusion

Le tri fusion s'appuie sur le fait que fusionner deux tableaux triés en un tableau trié se fait en un temps linéaire $O(n)$.

D'autres part, le découpage récursif d'un tableau jusqu'à arriver au cas terminal : tableau trié de un élément est en $\log(n)$. Ce qui fait bien une complexité en $O n\log(n)$, on ne peut pas faire mieux.

On va donc séparer notre algorithme en deux fonctions, une qui réalise la fusion et l'autre qui réalise la récursion du tri(le découpage). Ces deux opérations sont symbolisées sur l'illustration ci-dessous:

• rouge: division
• vert: fusion.

By VineetKumar at English Wikipedia - Transferred from en.wikipedia to Commons by Eric Bauman using CommonsHelper., Public Domain, Link

Algorithme de fusion

Voici l'algorithme de fusion de deux tableaux triés en un seul.

Tout d'abord en pseudo-code:

FUNCTION fusion(T1, T2)
    // T1 et T2 sont deux tableaux triés
    
    // Initialisation
    i1 <- 0   // indice du 1er tableau
    i2 <- 0   // indice du 2e tableau
    T <- []   // liste vide destinée à accueillir les éléments triés

    // Boucle
    TANT QUE l'on a pas atteint la fin d'un des tableaux
        SI T1[i1] <= T2[i2] ALORS
            Insérer T1[i1] à la fin de T
            incrémenter i1
        SINON
            Insérer T2[i2] à la fin de T
            incrémenter i2
        FIN SI
    FIN TANT QUE
    
    // Finalisation
    Insérer les éléments restants du tableau non vide à la fin de T
    
    RENVOYER T

Et voici une implémentation en python:

def fusion (T1, T2):
    # Initialisation
    N1, N2 = len(T1), len(T2)
    i1 = 0
    i2 = 0
    T = []

    # Boucle
    while (i1 < N1) and (i2 < N2):
        x1, x2 = T1[i1], T2[i2]
        if x1 <= x2:
            T.append(x1)
            i1 += 1
        else:
            T.append(x2)
            i2 += 1

    # Finalisation
    if i1 < N1:
        T += T1[i1:]
    if i2 < N2:
        T += T2[i2:]
    return T

Un petit test dans la console ipython permet de vérifier sur un cas simple la fusion:

>>> fusion([3,6,8], [2,5,7,12])
[2, 3, 5, 6, 7, 8, 12]

Algorithme de tri fusion

Voici l'algorithme récursif de tri fusion qui utilise la fonction fusion définie précédemment.

Tout d'abord en pseudo-code, on retrouve des techniques de découpage du tableau en deux avec des divisions entières // vues dans la recherche dichotomique.

FONCTION tri_fusion (T)
    N <- Longueur de T

    // Cas terminal
    SI N == 1 ALORS
        RENVOYER T
    FIN SI

    // Recursion sur les deux demi-tableaux sinon
    T1 <- tri_fusion(T[0:N//2]
    T2 <- tri_fusion(T[N//2:N]

    // Renvoi des la fusion des deux tableaux
    RENVOYER fusion(T1, T2)

Et voici une implémentation en python:

def tri_fusion (T):
    N = len(T)
    if N == 1:
        return T
    
    T1 = tri_fusion(T[:N//2])
    T2 = tri_fusion(T[N//2:])
    
    return fusion(T1, T2)

On fait un petit test sur une liste quelconque.

>>> tri_fusion([0, 25, 36, 41, 1, 465, 2, 3, 987])
[0, 1, 2, 3, 25, 36, 41, 465, 987]

Conclusion

Nous avons vu dans ce chapitre un algorithme particulièrement élégant et efficace pour trier des éléments. Bien sûr dans la pratique des contraintes de mémoire peuvent intervenir, et là au contraire cet algorithme se révélera peu performant, car l'utilisation de la récursivité et de la table $T$ intermédiaire le rend très gourmand en mémoire.

La méthode «diviser pour régner» est une méthode très efficace pour résoudre des problèmes complexes en les découpant en sous problèmes indépendants. Par contre, on verra dans le prochain chapitre qu'elle devient inefficace si les sous-problèmes se chevauchent, et il conviendra alors d'utiliser une nouvelle technique appelée « Programmation dynamique ».