Skip to content
Snippets Groups Projects
Select Git revision
  • 788852cafbd5754e502698f11f6d8e839e3e2a18
  • master default protected
2 results

load.py

Blame
  • Forked from Vuillemot Romain / INF-TC1
    Source project has a limited visibility.
    tri-fusion.py 1.87 KiB
    from random import seed, randint, shuffle
    
    def tri_split_merge(L) :
        """ TRI SPLIT-MERGE avec 2 fonctions imbriquées """
        def my_split(L) :
            choix=True              # on met dans L1, sinon dans L2 
            L1=[]; L2=[] ; N =len(L)
            i=0
            while i < N :
                crt=L[i]
                if choix : L1.append(crt)
                else : L2.append(crt)
                i +=1
                # voyons si on a une séquence Descendante
                while i < N and L[i] >= crt :
                    crt=L[i]
                    if choix : L1.append(crt)
                    else : L2.append(crt)
                    i +=1
                    
                choix = not choix
                
            return(L1,L2)
        
        #---------------------  
        def my_merge(L1,L2) :
            N1=len(L1)
            N2=len(L2)
            L=[]; i,j=0,0
            while(i < N1 and j < N2) :
                if L1[i] <= L2[j] : 
                    L.append(L1[i]) 
                    i+=1
                else :
                    L.append(L2[j]) 
                    j+=1
            L.extend(L1[i:])    # Ajouter le reste de L1 (s'il y en a) à L
            L.extend(L2[j:])    # Ajouter le reste de L2 (s'il y en a) à L
            return L
            
        # Fonction tri_split_merge
        while True :
            (L1,L2) = my_split(L)
            if (L2==[]) : break # Fini
            L=my_merge(L1,L2)  
        return L
            
    # programme principal -----------------------------------------------
    seed() # initialise le generateur de nombres aleatoires
    N=10
    L = [randint(2, N*4) for i in range(N)] # construction de la liste
    print("Avant le tri, liste = {}".format(L))
    L=tri_split_merge(L)
    print("Après le tri, liste = {}".format(L))
    
    """ Deux Traces
    Avant le tri, liste = [9, 17, 12, 24, 36, 26, 35, 25, 5, 31]
    Après le tri, liste = [5, 9, 12, 17, 24, 25, 26, 31, 35, 36]
    
    Avant le tri, liste = [30, 14, 2, 11, 5, 15, 5, 21, 29, 31]
    Après le tri, liste = [2, 5, 5, 11, 14, 15, 21, 29, 30, 31]
    """