TP : le tri fusion

TP : le tri fusion#

Le tri fusion d’un tableau de nombres est une application du principe diviser pour régner.

  • L’algorithme consiste à diviser ce tableau de nombres en 2 tableaux, puis chaque tableau en 2 nouveaux tableaux, etc.

  • Une fois les tableaux divisés jusqu’à avoir qu’une seule valeur, on recompose les tableaux par assemblage en triant les éléments.

Vous trouverez des informations sur la page wikipedia du tri fusion.

Diviser des tableaux#

On souhaite créer un tableau de valeurs à partir d’un autre tableau plus grand. Les valeurs sélectionnées se suivent dans le grand tableau ou sont séparées par un même nombre de valeurs.

Le slice est une technique en Python qui permet de sélectionner des éléments d’un tableau et se note avec les deux points.

Par exemple, pour extraire les valeurs d’un tableau t, on utilise la syntaxe : t[indice début:indice fin:écart].

Note

Voici trois règles utiles pour les slice des list Python:

  • Si l’indice de début est 0, on peut ne pas l’écrire.

  • Si l’indice de fin correspond à la dernière valeur, on peut laisser vide.

  • Si les valeurs à sélectionner se suivent, l’écart n’est pas nécessaire.

Soit t un tableau de 8 valeurs. Créer à partir de ce tableau :

  1. Un tableau sans la première et la dernière valeur;

  2. Un tableau composé de la première moitié de tableau;

  3. Un tableau composé de la seconde moitié de tableau;

  4. Un tableau avec les deux valeurs centrales;

  5. Un tableau avec les valeurs d’indices pairs;

  6. Un tableau avec les valeurs d’indices impairs;

Fusionner des tableaux#

La fusion de 2 tableaux peut se réaliser de plusieurs façons.

  1. La concaténation est une opération consistant à assembler deux tableaux en un seul. Le signe d’addition + est utilisé pour la concaténation.

    1. Concaténer les tableaux [3] et [5].

    2. Concaténer les tableaux [5] et [3].

    3. Concaténer les tableaux [3,7] et [5,8].

    4. Les tableaux obtenus par concaténation ont-ils leurs valeurs triées ? Pourquoi ?

  2. Il est possible de fusionner deux tableaux triés en un seul tableau trié. Pour y parvenir, il faut parcourir chaque tableau et insérer dans un nouveau tableau les valeurs en respectant l’ordre.

    1. En réalisant des schémas, décrire la fusion des tableaux [1,6,8] et [3,5].

    2. Écrire en Python une fonction fusion_tableaux qui prend en paramètre 2 tableaux triés et renvoie un tableau trié avec les valeurs des 2 tableaux passés en argument.

Le tri fusion#

L’algorithme se décompose en 2 temps. Le premier temps consiste à diviser le tableau en tableaux vides ou à 1 valeur. Le second temps consiste à fusionner les tableaux triés jusqu’à obtenir le tableau initial trié.

  1. Appliquer le tri fusion sur la liste L=[7,4,9,1,3,5,8] en donnant précisément les différentes étapes.

  2. On donne le script de la division:

    image

    Saisir et compléter ce code dans votre script Python.

  3. Écrire la fonction fusion qui effectue la fusion de 2 tableaux triés.

  4. Créer des listes aléatoires de nombres entiers puis vérifier que le tri fusion est bien réalisé.

Complexité du tri fusion#

On va comparer l’efficacité du tri fusion par rapport au tri par sélection et tri par insertion en mesurant les temps d’exécution de ces tris.

On donne le fichier Python mesure_tris.py qui contient :

  • la fonction tri_selection;

  • la fonction tri_insertion;

  • la fonction de mesure du temps d’exécution d’une fonction.

from random import randint
from time import time
from tri_fusion import fusion,tri_fusion

def tri_selection(tableau):
    i=0
    while i<len(tableau):
        k=i
        j=k
        while k < len(tableau):
            if tableau[k] < tableau[j]:
                j=k
            k=k+1
        tableau[i],tableau[j] = tableau[j],tableau[i]
        i=i+1
    return tableau

def tri_insertion(tableau):
    
    n = len(tableau)
    i = 1
    
    while i < n:
        j = i - 1
        tampon = tableau[i]

        while j >= 0 and tableau[j] > tampon:
            tableau[j+1] = tableau[j]
            j = j - 1
        
        tableau[j+1] = tampon
        i = i + 1
    return tableau


def mesure_tri(fct,n):
    
    tps = 0.0
    
    # on effectue 100 mesures de temps d'exécution de la fonction
    for _ in range(10):
        # on crée un tableau de dimension n
        t = [randint(0,100000) for i in range(n)]
        expression = fct + "(t)"
        
        # relevé du temps initial
        t_0 = time()
        
        # on exécute la fonction de tri
        eval(expression)

        # relevé du temps final
        t_1 = time()
        
        # on ajoute le temps d'exécution de la fonction
        tps = tps + (t_1-t_0)
    
    # on renvoie le temps moyen d'exécution de la fonction
    return tps/10


# on définit la taille du tableau
n = 4000
# on mesure les temps moyens d'exécution des tris
tps_selection = round(mesure_tri("tri_selection",n),3)
tps_insertion = round(mesure_tri("tri_insertion",n),3)
tps_fusion = round(mesure_tri("tri_fusion",n),3)
print(f"le temps de tri par insertion de {n} nombres est {tps_insertion} seconde")
print(f"le temps de tri par sélection de {n} nombres est {tps_selection} seconde")
print(f"le temps de tri fusion de {n} nombres est {tps_fusion} seconde")

  1. Effectuer des mesures sur les tris par sélection et par insertion d’un tableau de 1000 nombres.

  2. Importer la fonction tri_fusion puis effectuer des mesures de temps d’exécution de ce tri.

  3. Comparer la complexité des tris en comparant vos mesures.

Conclusion

  1. Les tris par selection et par insertion d’un tableau de dimension n ont des complexités \(O(n^{2})\).

  2. Le tri fusion d’un tableau de dimension n a une complexité \(O(n \log_{2}(n))\).

Par exemple, pour un tableau de 1000 nombres à trier, la complexité :

  • du tri par selection est d’ordre \(1000^{2}=1000000=10^{6}\)

  • du tri fusion est d’ordre \(1000 \times \log_{2}(1000) = 1000 \times 10 = 10^{4}\)

Cela signifie que le tri fusion est jusqu’à 100 fois plus efficace (rapide) que le tri par selection.