Ce blog est basé sur l'approche diviser pour conquérir. Merge Sort est un algorithme «diviser et conquérir» où le problème est divisé en sous-problèmes et est ensuite fusionné pour conquérir la solution. Ce blog sur le tri de fusion dans vous guidera à travers les sujets ci-dessous en détail -
comment arrêter un programme en java
- Qu'est-ce que le tri par fusion en Python?
- L'approche Divide and Conquer
- Implémentation du tri par fusion en Python
- Organigramme pour la mise en œuvre du tri par fusion
- Avantages et utilisation
Qu'est-ce que le tri par fusion en Python?
Le tri par fusion est basé sur l'algorithme de division et de conquête où le tableau d'entrée est divisé en deux moitiés, puis trié séparément et fusionné pour atteindre la solution. La fonction merge () est utilisée pour fusionner le trié .
L'approche Divide and Conquer
- Le tableau est divisé en deux et le processus est répété avec chaque moitié jusqu'à ce que chaque moitié soit de taille 1 ou 0.
- Le tableau de taille 1 est trié de manière simple.
- Maintenant, les deux tableaux triés sont combinés en un seul grand tableau. Et cela continue jusqu'à ce que tous les éléments soient combinés et que le tableau soit trié.
Voici une visualisation du tri de fusion pour effacer l'image pour vous
Tableau d'entrée = [3,1,4,1,5,9,2,6,5,4]
Maintenant, passons à la mise en œuvre.
Implémentation du tri par fusion en Python
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (moitié droite) i = j = k = 0 tandis que i Production:
$ python main.py
(«Fractionnement», [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(«Fractionnement», [3, 1, 4, 1, 5])
(«Fractionnement», [3, 1])
(«Fractionnement», [3])
(«Fusion», [3])
(«Fractionnement», [1])
(«Fusion», [1])
(«Fusion», [1, 3])
(«Fractionnement», [4, 1, 5])
(«Fractionnement», [4])
(«Fusion», [4])
(«Fractionnement», [1, 5])
(«Fractionnement», [1])
(«Fusion», [1])
(«Fractionnement», [5])
(«Fusion», [5])
(«Fusion», [1, 5])
(«Fusion», [1, 4, 5])
(«Fusion», [1, 1, 3, 4, 5])
(«Fractionnement», [9, 2, 6, 5, 4])
(«Fractionnement», [9, 2])
(«Fractionnement», [9])
(«Fusion», [9])
(«Fractionnement», [2])
(«Fusion», [2])
(«Fusion», [2, 9])
(«Fractionnement», [6, 5, 4])
(«Fractionnement», [6])
(«Fusion», [6])
(«Fractionnement», [5, 4])
(«Fractionnement», [5])
(«Fusion», [5])
(«Fractionnement», [4])
(«Fusion», [4])
(«Fusion», [4, 5])
(«Fusion», [4, 5, 6])
(«Fusion», [2, 4, 5, 6, 9])
(«Fusion», [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
élever quelque chose à une puissance en java
Organigramme pour la mise en œuvre du tri par fusion
Avantages et utilisation du tri par fusion
La plupart des autres algorithmes fonctionnent mal avec des structures de données séquentielles telles que des fichiers et des listes liées. Dans ces structures, l'accès à un élément aléatoire prend un temps linéaire et non un temps constant régulier. Et la nature du tri par fusion le rend facile et rapide pour de telles structures de données.L'une des meilleures caractéristiques du tri par fusion est son faible nombre de comparaisons. Cela fait O (n * log (n)) nombre de comparaisons, mais le facteur constant est bon par rapport au tri rapide, ce qui le rend utile lorsque la fonction de comparaison est une opération lente.En outre, l'approche diviser pour conquérir du tri par fusion facilite le traitement parallèle.
Avec cela, nous arrivons à la fin de ce blog sur «Comment implémenter le tri par fusion en Python». J'espère que le contenu a ajouté de la valeur à vos connaissances en Python. Pour obtenir des connaissances approfondies sur Python ainsi que sur ses différentes applications, vous pouvez vous inscrire en direct avec assistance 24/7 et accès à vie.