Tri fusion Python – implémentation de l’algorithme

Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c'est le cas.

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présente une implémentation du tri fusion python.

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présent une implémentation du tri fusion python.

Introduction

L’algorithme est le suivant :
Diviser en deux moitiés la liste à trier.
On trie chacune d’entre elles.
Fusionner les deux moitiés obtenues pour reconstituer la liste triée.

On applique récursivement cet algorithme c’est à dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.

tri fusion python
Tri fusion (source : wikipedia)
#Tri fusion fonction de division du tableau
def tri_fusion(tableau):
    if  len(tableau) <= 1: 
        return tableau
    pivot = len(tableau)//2
    tableau1 = tableau[:pivot]
    tableau2 = tableau[pivot:]
    gauche = tri_fusion(tableau1)
    droite = tri_fusion(tableau2)
    fusionne = fusion(gauche,droite)
    return fusionne


#Tri fusion fonction de fusion de 2 listes
def fusion(tableau1,tableau2):
    indice_tableau1 = 0
    indice_tableau2 = 0    
    taille_tableau1 = len(tableau1)
    taille_tableau2 = len(tableau2)
    tableau_fusionne = []
    while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
        if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
            tableau_fusionne.append(tableau1[indice_tableau1])
            indice_tableau1 += 1
        else:
            tableau_fusionne.append(tableau2[indice_tableau2])
            indice_tableau2 += 1
    while indice_tableau1<taille_tableau1:
        tableau_fusionne.append(tableau1[indice_tableau1])
        indice_tableau1+=1
    while indice_tableau2<taille_tableau2:
        tableau_fusionne.append(tableau2[indice_tableau2])
        indice_tableau2+=1
    return tableau_fusionne

tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
tableau_trie = tri_fusion(tableau)
print(tableau_trie)

A propos de tri fusion

Enfin, Le tri fusion fonctionne par comparaison. La complexité de l’algorithme pour n entrée est n log n, donc asymptotiquement optimal.

La technique est de diviser pour régner. Et l’algorithme fait principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire).

Tri fusion python : liens externes

https://www.geeksforgeeks.org/merge-sort/

http://lwh.free.fr/pages/algo/tri/tri_fusion.html

https://pixees.fr/informatiquelycee/n_site/isn_algo_diviser_pour_regner.html

https://fr.wikipedia.org/wiki/Tri_fusion

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.

Une réflexion sur « Tri fusion Python – implémentation de l’algorithme »

Les commentaires sont fermés.