Tri-fusion

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

1. http://www.youtube.com/watch?v=OEmlVnH3aUg
2. http://www.youtube.com/watch?v=XaqR3G_NVoo