Le tri par fusion démystifié : un guide du débutant pour diviser pour mieux régner

Le tri par fusion a été introduit par John von Neumann en 1945, principalement pour améliorer l'efficacité du tri de grands ensembles de données. L'algorithme de Von Neumann visait à fournir un processus de tri cohérent et prévisible en utilisant la méthode diviser pour régner. Cette stratégie permet au Merge Sort de gérer efficacement des ensembles de données petits et grands, garantissant un tri stable avec une complexité temporelle de O(n log n) dans tous les cas.

Merge Sort utilise l'approche diviser pour régner, qui divise le tableau en sous-tableaux plus petits, les trie de manière récursive, puis fusionne les tableaux triés ensemble. Cette approche divise le problème en morceaux gérables, en triant chaque morceau individuellement et en les combinant efficacement. En conséquence, l'algorithme fonctionne bien même sur de grands ensembles de données en divisant la charge de travail de tri.

La récursion est un processus dans lequel une fonction s'appelle pour résoudre une version plus petite du même problème. Il continue de décomposer le problème jusqu'à ce qu'il atteigne un point où le problème est suffisamment simple pour être résolu directement, ce que l'on appelle le cas de base.

Vous trouverez ci-dessous une implémentation de Merge Sort en JavaScript, montrant comment le tableau est divisé et fusionné de manière récursive :

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

Pour mieux comprendre le fonctionnement du tri par fusion, passons en revue le processus en utilisant le tableau : [38, 27, 43, 3, 9, 82, 10]

Étape 1 : Division récursive (fonction mergeSort)
Le tableau est divisé de manière récursive en sous-tableaux plus petits jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément. Cela se produit via les lignes suivantes dans la fonction mergeSort :

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

Cela arrête notre récursion.

Voici comment se déroule la division récursive :

• Appel initial : mergeSort([38, 27, 43, 3, 9, 82, 10])
  • Le tableau est divisé au milieu : [38, 27, 43] et [3, 9, 82, 10]

• Première mi-temps :

  • fusionTri([38, 27, 43])
    • Split au milieu : [38] et [27, 43]
  • fusionTri([27, 43])
    • Divisé en [27] et [43]
  • Les sous-tableaux [38], [27] et [43] sont maintenant des éléments individuels et prêts à être fusionnés.

• Deuxième mi-temps :

  • fusionTri([3, 9, 82, 10])
    • Partage au milieu : [3, 9] et [82, 10]
  • fusionTri([3, 9])
    • Divisé en [3] et [9]
  • fusionTri([82, 10])
    • Divisé en [82] et [10]
  • Les sous-tableaux [3], [9], [82] et [10] sont maintenant prêts à être fusionnés.

Étape 2 : Fusionner les sous-tableaux triés (fonction de fusion)
Maintenant, nous commençons à fusionner les sous-tableaux dans un ordre trié à l'aide de la fonction de fusion :

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

Voici comment fonctionne le processus de fusion :

Première fusion (à partir des cas de base) :

• Fusionner [27] et [43] → Le résultat est [27, 43]
• Fusionner [38] avec [27, 43] → Le résultat est [27, 38, 43]

À ce stade, la moitié gauche du tableau est entièrement fusionnée : [27, 38, 43].

Deuxième fusion (à partir des cas de base) :

• Fusionner [3] et [9] → Le résultat est [3, 9]
• Fusionner [82] et [10] → Le résultat est [10, 82]
• Fusionner [3, 9] avec [10, 82] → Le résultat est [3, 9, 10, 82]

Maintenant, la moitié droite est entièrement fusionnée : [3, 9, 10, 82].

Étape 3 : Fusion finale
Enfin, les deux moitiés [27, 38, 43] et [3, 9, 10, 82] sont fusionnées à l'aide de la fonction de fusion :

Comparez 27 (gauche[0]) et 3 (droite[0]). Depuis 3 < 27, ajoutez 3 au résultat.
Comparez 27 et 9. Ajoutez 9 au résultat.
Comparez 27 et 10. Ajoutez 10 au résultat.
Comparez 27 et 82. Ajoutez 27 au résultat.
Comparez 38 et 82. Ajoutez 38 au résultat.
Comparez 43 et 82. Ajoutez 43 au résultat.
Ajoutez l'élément 82 restant du tableau de droite.
Le tableau entièrement fusionné et trié est :
[3, 9, 10, 27, 38, 43, 82].

Complexité temporelle : Meilleur, moyen et pire cas : O(n log n)
Regardons ça de plus près :

Division (O(log n)) : chaque fois que le tableau est divisé en deux moitiés, la taille du problème est réduite. Puisque le tableau est divisé en deux à chaque étape, le nombre de fois que vous pouvez le faire est proportionnel au log n. Par exemple, si vous avez 8 éléments, vous pouvez les diviser en deux 3 fois (puisque log₂(8) = 3).

Fusion (O(n)) : après avoir divisé le tableau, l'algorithme fusionne les tableaux plus petits dans l'ordre. La fusion de deux tableaux triés de taille n prend un temps O(n) car vous devez comparer et combiner chaque élément une fois.

Complexité globale (O(n log n)) : Puisque la division prend O(log n) étapes et que vous fusionnez n éléments à chaque étape, la complexité temporelle totale est la multiplication de ces deux : O(n log n).

Complexité spatiale : O(n)
Le tri par fusion nécessite un espace supplémentaire proportionnel à la taille du tableau car il nécessite des tableaux temporaires pour stocker les éléments pendant la phase de fusion.

Comparaison avec d'autres algorithmes de tri :
QuickSort : bien que QuickSort ait une complexité temporelle moyenne de O(n log n), son pire cas peut être O(n^2). Le tri par fusion évite ce pire scénario, mais QuickSort est généralement plus rapide pour le tri en mémoire lorsque l'espace est un problème.
Tri à bulles : beaucoup moins efficace que le tri par fusion, avec une complexité temporelle de O(n^2) pour les scénarios moyens et les pires.

Utilisation dans le monde réel
Le tri par fusion est largement utilisé pour le tri externe, où de grands ensembles de données doivent être triés à partir du disque, car il gère efficacement les données qui ne rentrent pas dans la mémoire. Il est également couramment implémenté dans des environnements informatiques parallèles, où les sous-réseaux peuvent être triés indépendamment, en tirant parti du traitement multicœur.

De plus, des bibliothèques et des langages tels que Python (Timsort), Java et C (std::stable_sort) s'appuient sur des variantes de Merge Sort pour garantir la stabilité des opérations de tri, ce qui le rend particulièrement adapté au tri d'objets et de structures de données complexes.

Conclusion
Merge Sort continue d'être un algorithme fondamental à la fois en informatique théorique et dans les applications pratiques en raison de sa stabilité, de ses performances constantes et de son adaptabilité pour le tri de grands ensembles de données. Alors que d'autres algorithmes comme QuickSort peuvent fonctionner plus rapidement dans certaines situations, la complexité temporelle et la polyvalence garanties O(n log n) de Merge Sort le rendent inestimable pour les environnements à mémoire limitée et pour maintenir l'ordre des éléments avec des clés égales. Son rôle dans les bibliothèques de programmation modernes garantit qu'il reste pertinent dans les applications du monde réel.

Sources :

1. Knuth, Donald E. L'art de la programmation informatique, Vol. 3 : Tri et recherche. Addison-Wesley Professional, 1997, pp. 158-160.
2. Cormen, Thomas H., et al. Introduction aux algorithmes. MIT Press, 2009, Chapitre 2 (Tri par fusion), Chapitre 5 (Complexité de l'algorithme), Chapitre 7 (Tri rapide).
3. Silberschatz, Abraham et al. Concepts du système de base de données. McGraw-Hill, 2010, chapitre 13 (Tri externe).
4. "Timsort." Documentation Python, Python Software Foundation. Timsort de Python
5. "Java Arrays.sort." Documentation Oracle. Arrays.sort() de Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!