Informatique au lycée Faustin Fleret

En première, nous avons vu deux algorithmes :

• 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 ou très peu utilisés en pratique car peu efficaces. Il existe une méthode pour trier plus efficace que nous allons découvrir

Diviser pour régner est le nom d'une méthode de calcul inventée par Euclide au IIIe siècle avant J-c.

Diviser pour régner est une méthode algorithmique basée sur le principe suivant : On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes.
La notion de récursivité est aussi nécessaire dans cette méthode.

Méthode « diviser pour régner » :

La méthode diviser pour régner consiste, pour résoudre un problème complexe de taille N, à :

• (Diviser) : partager le problème en sous-problèmes (par exemple de taille N/2)
• (Régner) : résoudre ces différents sous-problèmes (généralement récursivement)
• (Combiner) : fusionner les solutions pour obtenir la solution du problème initial

On obtient en général moins d'appels récursifs. Dans certains cas la méthode diviser pour régner donne un algorithme de résolution plus rapide.

L'idée étant que les "petits problèmes" seront plus simples à résoudre que le problème original. Une fois les petits problèmes résolus, on recombine les "petits problèmes résolus" afin d'obtenir la solution du problème de départ.

Exemple

Pour calculer 2^6 à l'aide de la méthode "Diviser pour régner", on peut diviser le problème en deux parties égales : 2^3 et 2^3. On peut ensuite diviser chacune de ces parties en deux parties égales : 2^2 et 2^1, et résoudre chaque partie de manière récursive. Enfin, on combine les résultats pour obtenir le résultat final.

Plus précisément, voici les étapes pour calculer 2^6 à l'aide de cette méthode :

• Diviser le problème en deux parties égales : 2^3 et 2^3.
• Diviser chaque partie en deux parties égales : 2^2 et 2^1.
• Résoudre chaque partie de manière récursive : 2^1 = 2 2^2 = 2 * 2 = 4 2^3 = 2^2 * 2^1 = 4 * 2 = 8
• Combiner les résultats pour obtenir le résultat final : 2^6 = 2^3 * 2^3 = 8 * 8 = 64.

Ainsi, la méthode "Diviser pour régner" permet de résoudre le problème de manière efficace en le décomposant en sous-problèmes plus petits et en combinant les résultats. Cela peut être utile pour résoudre des problèmes complexes tels que le calcul de puissances élevées.

Implémentation en Python du “diviser pour régner”

Nous allons écrire une fonction “puissance(x,n)” basée sur ce paradigme, où x et n sont deux entiers (positif pour n). Pour cela, nous allons prendre en compte que:

• si n=0, alors xⁿ = 1.
• si n est pair, alors x ⁿ = (x^n/2)²
• si n est impair, alors x ⁿ = x * (x^n/2)²

Cela donne alors la fonction suivante (exponentiation rapide):

def expo_rapide(x,n):
	"""
    Renvoie xn
    :param:   n (int) et x (int)
    :return: un entier
    :CU: n>=0
    """
	if n == 0:
		return 1
	elif n % 2 == 0:
		return expo_rapide(x * x,n // 2)
	else:
		return x*expo_rapide(x * x, n // 2)

Le tri fusion

Le tri fusion découvert par John von Neumann en 1945 consiste à trier récursivement les deux moitiés de la liste, puis à fusionner ces deux sous-listes triées en une seule. La condition d’arrêt à la récursivité sera l’obtention d'une liste à un seul élément, car une telle liste est évidemment déjà triée.

Voici donc les trois étapes (diviser, régner et combiner) de cet algorithme :

1. Diviser la liste en deux sous-listes de même taille (à un élément près) en la "coupant" par la moitié.
2. Trier récursivement chacune de ces deux sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.
3. Fusionner les deux sous-listes triées en une seule.

On considère la liste suivante de sept entiers :

On la scinde en deux sous-listes en la coupant par la moitié :

Sous-listes que l’on scinde à leur tour :

Sous-listes que l’on scinde à leur tour :

Ces sous-listes sont triées car elles n’ont qu’un élément. On va maintenant les fusionner deux par deux en de nouvelles sous-listes triées :

De nouveau une étape de fusionnement :

Une dernière fusion :

On a fusionné toutes les sous-listes obtenues lors des appels récursifs, le tri est terminé :

Regardons l'algorithme de fusion de deux tableaux triés.

FONCTION 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 l'algorithme récursif de tri fusion qui utilise la fonction fusion définie précédemment..

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)

Comparons avec les tris connus:

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)