Aperçu des algorithmes de tri Tri fusion

Algorithmes de tri fusion

Comprendre comment le paradigme de la division et de la conquête peut être appliqué au tri

Introduction

En ce qui concerne le tri, le tri fusion est l’un des algorithmes les plus populaires. Il est basé sur le célèbre paradigme “diviser pour régner” où un grand problème est divisé en problèmes plus petits qui sont plus faciles à résoudre. Les solutions à ces problèmes sont ensuite combinées pour le problème original.

Dans ce tutoriel, nous plongerons dans les détails de l’implémentation et estimerons la complexité du tri fusion en termes de notation Big O. Un exemple sera également fourni pour une meilleure compréhension.

Algorithme

L’idée de l’algorithme est de commencer par trier de manière récursive de plus petits sous-tableaux du tableau d’origine. Lorsque plusieurs sous-tableaux sont triés, ils sont transformés en un nouveau tableau de taille plus grande. Cette procédure se poursuit jusqu’à ce que nous obtenions la version triée du tableau initial.

• Aperçu des algorithmes de tri Tri par tas
• Vue d’ensemble des algorithmes de tri Quicksort
• Le Guide Ultime pour Entraîner BERT à partir de Zéro Préparer le Jeu de Données

Cela peut sembler trop compliqué au début, mais il s’avère que l’obtention d’un nouveau tableau trié à partir de tableaux déjà triés est une procédure relativement rapide.

Nous allons commencer par examiner la fonction de fusion. Ensuite, nous l’utiliserons pour la version finale de l’algorithme.

Fonction de fusion

La fonction de fusion prend deux sous-tableaux triés et renvoie un nouveau tableau trié composé d’éléments des deux sous-tableaux. Dans l’extrait de code ci-dessous, un tableau d’éléments est passé avec deux sous-tableaux triés array[left, middle] et array[middle + 1, right].

Fonction de fusion

Nous parcourons les éléments des deux tableaux en utilisant deux pointeurs : i et j. En comparant les éléments array[i] et array[j] à chaque itération, nous ajoutons l’élément le plus petit à new_array. Ensuite, un pointeur i ou j est augmenté en fonction de l’élément ajouté afin qu’il puisse pointer vers l’élément suivant.

La boucle dure jusqu’au moment où tous les éléments de l’un ou l’autre sous-tableau ont été ajoutés à new_array. Ensuite, nous ajoutons simplement les éléments restants contenant des valeurs plus grandes d’un autre sous-tableau.

Enfin, nous copions chaque élément du nouveau tableau trié dans le tableau d’origine. Par conséquent, tous les éléments des indices left à right sont triés dans le tableau.

Notons que pour deux sous-tableaux de longueur N, nous parcourons linéairement chaque élément une seule fois. Cela donne une complexité de O(N) pour cette méthode.

Exemple de fusion

Supposons que nous ayons un tableau composé de deux sous-tableaux triés array[0:3] et array[4:7]. Tout d’abord, nous initialisons deux pointeurs i et j qui pointent vers les éléments les plus petits. Dans notre cas, ils pointent vers les éléments avec les indices 0 et 4 respectivement.

Itération 1. Nous comparons array[0] = 2 et array[4] = 3. Comme 2 ≤ 3, nous enregistrons 2 comme premier élément du nouveau tableau et incrémentons i de 1, de sorte qu’il pointe vers le prochain élément croissant qui est 9.

Itération 2. Nous comparons array[1] = 9 et array[4] = 3. Comme 9 > 3, nous enregistrons 3 comme deuxième élément du nouveau tableau et incrémentons j de 1, de sorte qu’il pointe vers le prochain élément croissant qui est 7.

Itération 3. array[1] = 9 > array[5] = 7. Nous enregistrons 7 comme élément suivant. j est incrémenté de 1.

…

Itération 7. j pointe vers la fin du sous-tableau droit. Cela signifie que tous les éléments à partir de l’index i dans le sous-tableau gauche sont supérieurs à tous les éléments du sous-tableau droit. Par conséquent, nous copions tous les éléments restants (16 et 20) du sous-tableau droit dans le nouveau tableau.

Une fois cette procédure terminée, toutes les valeurs triées du nouveau tableau sont ensuite copiées dans le tableau d’origine.

Fonction de tri

La fonction de tri appelle récursivement elle-même pour trier séparément ses moitiés gauche et droite. Lorsque les deux moitiés sont triées, elles sont jointes après l’appel de la fonction merge_sort().

Fonction merge sort

Pour rendre l’interface d’une fonction plus pratique pour un client, le premier appel de la fonction merge_sort() peut être enveloppé dans une autre fonction. Ainsi, le client n’a pas besoin de passer les arguments gauche et droit de la fonction, ce qui suit avec succès le principe de conception de l’encapsulation.

Envelopper l’appel merge sort dans une autre fonction

Exemple

L’appel hiérarchique du merge sort pour un tableau avec 8 éléments est illustré dans la figure ci-dessous. Tout d’abord, nous divisons le tableau en deux parties égales de longueur 4. Pour chacune des moitiés, nous appelons à nouveau le merge sort. Cela donne des tableaux de taille 2. Au fait, il n’est pas nécessaire de diviser ces tableaux à nouveau car tout tableau composé d’un seul élément est toujours trié.

Nous continuons l’algorithme en triant les tableaux de taille 2. Une fois que deux tableaux séquentiels de taille 2 sont triés, ils sont fusionnés en un nouveau tableau trié de longueur 4. Ce processus dure pour tous les tableaux de taille 2. Une fois que deux tableaux séquentiels de taille 4 sont triés, ils sont fusionnés de manière analogue en un nouveau tableau trié de longueur 8.

Nous terminons la procédure lorsque tous les éléments sont triés.

Complexité

Pour évaluer la complexité, nous devons d’abord comprendre la structure des appels récursifs. Supposons que nous ayons un tableau de taille N qui doit être trié.

Nous divisons ce tableau en deux moitiés de taille N / 2. Les deux moitiés sont ensuite divisées en deux moitiés plus petites de taille N / 4. En conséquence, nous obtenons 4 tableaux de taille N / 4. De même, au niveau suivant, nous obtenons 8 tableaux de taille N / 8. Nous continuons cette procédure jusqu’à ce que nous atteignions N tableaux de taille 1. Ce processus est illustré dans la figure suivante.

Pour chacun des tableaux illustrés, nous devons appeler une procédure de fusion qui nécessite un temps O(K) où K est la longueur du tableau. Calculons la complexité temporelle totale pour chaque niveau de tableaux dans la figure ci-dessus.

• Pour le premier niveau, nous avons un seul tableau de taille N qui nécessite un temps de traitement O(N).
• Pour le deuxième niveau, nous avons 2 tableaux de taille N / 2. Chacun de ces tableaux nécessite un temps O(N / 2). Le temps total est de 2 * O(N / 2) = O(N).
• Pour le troisième niveau, nous avons 4 tableaux de taille N / 4. Chacun de ces tableaux nécessite un temps O(N / 4). Le temps total est de 4 * O(N / 2) = O(N).
• Le dernier niveau contient N tableaux de taille 1. Chacun de ces tableaux nécessite un temps O(1). Le temps total est de N * O(1) = O(N).

En suivant cette logique, il est clair que chaque niveau nécessite un temps de traitement O(N). Étant donné qu’à chaque étape, chaque tableau est divisé en deux moitiés, il est facile de remarquer qu’il y a O(logN) niveaux. Cela donne une complexité temporelle finale de O(N) * O(logN) = O(N * logN).

Avantages

• Efficacité. Le merge sort a une complexité globale de O(N * logN). C’est la meilleure complexité possible parmi tous les algorithmes de tri basés sur la comparaison des éléments du tableau. Cependant, lors de la procédure de fusion, les éléments doivent être temporairement triés dans un autre tableau. La taille de ce tableau est identique à la longueur des deux sous-tableaux, ce qui nécessite un espace mémoire de O(N).
• Simplicité. Comparé à d’autres algorithmes de tri efficaces, le merge sort peut être facilement interprété et implémenté.
• Tri stable. Si un tableau initial a des éléments égaux, alors l’algorithme de merge sort ne changera pas leur position relative. C’est une propriété importante utilisée par des algorithmes plus complexes ayant une partie de tri dans leur implémentation.

Conclusion

Nous avons examiné l’un des algorithmes de tri les plus populaires qui nous a aidés à comprendre le principe du paradigme diviser-pour-régner. En plus de cela, le tri fusion combine élégamment sa simplicité avec une complexité efficace et est utilisé dans un grand nombre d’applications.

Toutes les images, sauf indication contraire, sont de l’auteur.

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!