Select Git revision
-
Romain Vuillemot authoredRomain Vuillemot authored
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]
"""