méthode "diviser pour régner"

Objectif :

À la fin de cette séquence vous serez capable d'écrire un algorithme utilisant la méthode « diviser pour régner ».

Principe :
La méthode (on dit aussi le paradigme) "diviser pour régner" est une technique de programmation qui procède en trois étapes :

• Découper : le problème de départ en plusieurs sous-problèmes semblables au problème initial mais de taille moindre.
• Régner : sur les sous-problèmes en les résolvant séparément de manière récursive.
• Combiner : les solutions des sous-problèmes pour produire la solution du problème originel.

Tri fusion

John von Neumann est à l'origine de l'algorithme du tri par fusion (merge sort en anglais) mais ce dernier a été amélioré et implémenté par les mathématiciens américains Lester Randolph Ford Jr. et Selmer M. Johnson.
Principe :

• On sépare la liste à trier en deux listes deux fois plus petites ; Cela est répété de manière récursive jusqu'à ce que chaque sous-liste contienne un seul élément.
• On trie récursivement chaque moitié de la liste ;
• On fusionne les deux listes pour obtenir une liste triée. Cela est généralement réalisé en comparant les éléments et en les fusionnant dans l'ordre.

1. Fonction fusion

La fonction fusion permet de fusionner deux sous-listes triées.

Une illustration :

Algorithme de la fusion de deux tableaux triés :

Fonction fusion(gauche, droite)

        """
            gauche et droite sont deux tableaux triés.
            La fonction renvoie, dans un tableau, les éléments de gauche et droite triés. 
        """

    Tant que gauche n'est pas vide et droite n'est pas vide :
        Si le premier élément de gauche est inférieur ou égal au premier élément de droite :
            Ajouter le premier élément de gauche au résultat
        Sinon:
            Ajouter le premier élément de droite au résultat
    FinTant que

    Ajouter le reste de gauche ou de droite au résultat

    Renvoyer le résultat

Pseudo-code

Fonction fusion(gauche, droite)

        """
            gauche et droite sont deux tableaux triés.
            La fonction renvoie, dans un tableau, les éléments de gauche et droite triés. 
        """

        gauche est un tableau de n1 éléments
        droite est un tableau de n2 éléments
        resultat est est un tableau vide
        i1 ← 0
        i2 ← 0

        Tant que i1 < n1 et i2 < n2 Faire:
            Si gauche[i1] < droite[i1] Alors,
                resultat ← gauche[i1]
                i1 ← i1 + 1
            Sinon
                resultat ← droite[i2]
                i2 ← i2 + 1
            FinSi
        FinTant que

        #Une des listes est vide
        Si i1 < n1, Alors,
            Tant que i1 < n1 Faire:
                Ajouter les éléments de gauche au resultat
            FinTant que
        FinSi

        Si i2 < n2, Alors,
            Tant que i2 < n2, Faire:
                Ajouter les éléments de droite au résultat
            FinTant que
        FinSi                         

En Python

def fusion(gauche:list, droite:list)->list:
    """
        Entrées : gauche et droite sont deux listes de nombres triés dans l'ordre croissant
        Sortie : une liste triée résultant de gauche et droite
    """
    resultat = []
    n1 = len(gauche)
    n2 = len(droite)
    i1 = i2 = 0
    
    while i1 < n1 and i2 < n2:#Tant qu'aucune des deux listes n'est vide
        if gauche[i1] < droite[i2]:
            resultat.append(gauche[i1])
            i1 += 1
        else:
            resultat.append(droite[i2])
            i2 += 1
    
    #Une des listes est vide
    if i1 < n1: #droite est vide
        while i1 < n1:
            resultat.append(gauche[i1])
            i1 += 1

    else: #gauche est vide
        while i2 < n2:
            resultat.append(droite[i2])
            i2 += 1

    return resultat

2. Fonction tri fusion

Une illustration :

Algorithme de la fonction tri_fusion :

Fonction tri_fusion(tab)

        """
            tab est un tableau.
            La fonction renvoie tab trié. 
        """

        Si la longueur de tab est inférieure ou égale à 1:
            Renvoyer tab
        Sinon:
            Diviser tab en deux moitiés
            Trier récursivement chacune des deux moitiés
            Fusionner et renvoyer les deux moitiés triées

Pseudo-code

Fonction tri_fusion(tab)

        """
            tab est un tableau.
            La fonction renvoie une permutation triée de tab. 
        """

        tab est un tableau de n éléments

        Si n ≤ 1, Alors,
            Renvoyer tab
        Sinon :
            Diviser tab en deux moitiés
            # Trier récursivement chacune des deux moitiés
            gauche  ←  tri_fusion(moitié gauche de tab)
            droite  ←  tri_fusion(moitié droite de tab)
            # Fusionner et renvoyer les deux moitiés triées
            Renvoyer fusion(gauche, droite)   
        FinSi

En Python

#Tri fusion
def tri_fusion(lst):
    n = len(lst)
    if len(lst) <= 1: #cas de base
        return lst
    else:
        milieu = len(lst) // 2
        lst_gauche = tri_fusion(lst[:milieu])
        lst_droite = tri_fusion(lst[milieu:])
        
        return fusion(lst_gauche, lst_droite)

3. Complexité temporelle de la fonction tri_fusion

Le tri par fusion a une complexité logarithmique, O(nlogn), où n est la taille du tableau.
Comparaison avec les tris par sélection et par insertion.
Dans le pire cas, le tri par sélection et le tri par insertion ont une complexité temporelle quadratique, O(n²), où n est la taille du tableau.
Par conséquent, en termes de complexité temporelle, dans le pire cas, le tri par fusion est généralement plus efficace que le tri par sélection et le tri par insertion, surtout pour des tableaux de grande taille.