This page was exported from Enseignement de l'informatique et du numérique au lycée Boissy d'Anglas [ https://icn-isn-boissy.yj.fr/wp ]

Export date:Fri Apr 18 5:23:44 2025 / +0000 GMT

___________________________________________________


Title: Tri-fusion

---------------------------------------------------




 YouTube Video: YouTube.com/watch?v=OEmlVnH3aUg 




Etudions d'abord l'algorithme de la fusion de 2 listes:



FUSIONNER (`liste_gauche`, `liste_droite`):* On parcourt les deux listes `gauche` et `droite` en même temps,Pour chaque paire d'éléments, on place le plus petit dans liste resultat.* S'il reste des éléments dans `gauche` ou dans `droite` on les place à la fin de liste resultat



Développement graphique:



Soit 2 listes à fusionner:



Liste gauche : [3, 1, 4, 7, 8] et la liste droite : [2, 5, 6]















implémenter sous pyzo la fonction FUSIONNE donc voici le début:



def fusionne(lst1, lst2):
    """
    list1 est une liste 
    list2 est une liste 
    la fonction retourne une liste resultat fusion des 2 listes list1 et list2
    Example
    -------
    >>> fusionne([3, 1, 4, 7, 8], [2, 5, 6])
 # listes non ordonnées
    [2, 3, 1, 4, 5, 6, 7, 8]

    >>> fusionne([1, 3, 4, 7, 8], [2, 5, 6])
 # listes ordonnées
    [1, 2, 3, 4, 5, 6, 7, 8]
    """



Maintenant regardons  l'algorithme de la fonction TRI FUSION



TRI FUSION (liste):• Si liste est de taille <= 1 on ne fait rien.• Sinon, On sépare liste en 2 parties gauche et droite,• On appelle Tri fusion sur gauche et sur droite• On fusionne gauche et droite dans liste



Développement graphique :



Soit la liste [2, 3, 1, 4, 5, 6, 7, 8] à trier par fusion



on sépare d'abord :







et on fusionne avec la fonction FUSIONNE décrite juste avant:







implémenter cette fonction 



def fusionne(lst1, lst2):
    """
    list1 est une liste 
    list2 est une liste 
    la fonction retourne une liste resultat fusion des 2 listes list1 et list2
    Example
    -------
    >>> fusionne([3, 1, 4, 7, 8], [2, 5, 6])
 # listes non ordonnées
    [2, 3, 1, 4, 5, 6, 7, 8]

    >>> fusionne([1, 3, 4, 7, 8], [2, 5, 6])
 # listes ordonnées
    [1, 2, 3, 4, 5, 6, 7, 8]
    """



def tri_fusion(lst):
    '''lst est une liste non triées
       Elle est coupé en 2 listes gauche et droite par le milieu (ou presque si taille impaire),
       puis la fonction tri_fusion est rappelée pour chaque liste gauche et droite, jusqu'à n'obtenir des listes de taille 1.
       en fin on applique la fonction fusionne les listes gauche et droite dans une liste  que la fonction renvoie.

       Exemple:
       >>> tri_fusion([2, 3, 1, 4, 5, 6, 7, 8])
       [1, 2, 3, 4, 5, 6, 7, 8]'''''




voici un programme pour créer des listes triées ou aléatoire pour faire des tests:



import random

def liste_triee(nb):#Création d'une liste trièe dans l'ordre croissant de nb valeur
    nmax=nb
    L=[]
    for i in range(0,nmax):
        L.append(i)
    return L


def liste_aleatoire(nb):# fabrication d'une liste de nb valeurs aléatoires
    nmax=nb
    L=[]
    for i in range(0,nmax):
        L.append(random.randint(0,nmax))
    return L




 YouTube Video: YouTube.com/watch?v=XaqR3G_NVoo 



---------------------------------------------------


Images: https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2021/02/f1.png

https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2021/02/f2.png

https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2021/02/f3.png

https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2021/02/f4-1.png

https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2021/02/f5.png



---------------------------------------------------




---------------------------------------------------


Post date: 2020-12-16 10:12:24

Post date GMT: 2020-12-16 09:12:24

Post modified date: 2021-12-10 08:29:59

Post modified date GMT: 2021-12-10 07:29:59



____________________________________________________________________________________________


Export of Post and Page as text file has been powered by [ Universal Post Manager ] plugin from www.gconverters.com