Tri par fusion - Exercices

Fusion manuelle.

Soit L=[45, 2, 4, 6, -5, 4, 3, 24, 7, 2]

Écrire les différents états de la liste L lors du déroulement d'un tri par fusion.

Résolution de l'exercice "Fusion manuelle".

L=[45, 2, 4, 6, -5, 4, 3, 24, 7, 2]
L=[2, 45, 4, 6, -5, 4, 3, 24, 2, 7 ]
L=[2, 4, 6, 45 , -5, 3, 4, 24, 2, 7 ]
L=[-5, 2, 3, 4, 4, 6, 24, 45 , 2, 7 ]
L=[-5, 2, 2, 3, 4, 4, 6, 7, 24, 45 ]

Programmer une fusion.

Programmer l'algorithme suivant :


Entrée : une liste L de nombres, trois entiers p, q, r tels que 
				a) p < q < r 
				b) les sous-listes [L_p, L_p+1, ..., L_q-1] 
				   et [L_q, L_q+1, ..., L_r-1] sont triées.
 
Sortie : la liste L dans laquelle les sous-listes  [L_p, L_p+1, ..., L_q-1] 
et [L_q, L_q+1, ..., L_r-1] on été fusionnées.

Résolution de l'exercice "Programmer une fusion".

Une première version utilisant quelques raccourcis python (au risque de manipulations intermédiaires de listes consommatrices de temps en mémoire) :


def fusion(L, p, q, r) :
	L3 = []
	L1 = L[p:q]
	L2 = L[q:r]
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while L1 and L2 :
		if L1[0]<L2[0] : L3.append(L1.pop(0))
		else : L3.append(L2.pop(0))
			
	# une sous-liste étant vidée
	# on colle tout le contenu 
	# non encore traité de l'autre sous-liste
	# en queue de L3 
	if L1 : L3.extend(L1)
	else : L3.extend(L2)
			
	# on copie dans la liste L initiale
	# la fusion obtenue :
	del(L[p:q])
	L[p:q]=L3
		
	
# exemple d'utilisation : 
L = [2,18,15, 2,5,6,9,  5,7,8,11,  -5,12]
print(L)
fusion(L, 3, 7, 11)
print(L)

Cette seconde version évite les défauts évoqués :


def fusion(L, p, q, r) :
	L3 = []
	i, j = p, q
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while i<q and j<r :
		if L[i]<L[j] :
			mini = L[i]
			L3.append(L[i])
			i+=1
		else :
			mini = L[j]
			L3.append(L[j])
			j+=1
			
	# une sous-liste étant vidée
	# on colle tout le contenu 
	# non encore traité de l'autre sous-liste
	# en queue de L3 
	if i == q : 
		for k in range(j, r) :
			L3.append(L[k])
	else :
		for k in range(i, q) :
			L3.append(L[k])
			
	# on copie dans la liste L initiale
	# la fusion obtenue :
	for k in range(p, r) :
		L[k]=L3[k-p]
		
	
# exemple d'utilisation : 
L = [2,8,1, 2,5,6,9,  5,7,8,11,  -5,12]
print(L)
fusion(L, 3, 7, 11)
print(L)

Programmer le tri par fusion.

Liste triée k par k.

On dira qu'une liste est triée k par k si les 'segments' successifs de longueur k dans la liste sont triés, c'est à dire L₀ ≤ L₁ ≤ ... ≤ L_k-1 puis L_k ≤ L_k+1 ≤ ... ≤ L_2k-1 puis ... (le dernier segment étant éventuellement de longueur inférieure à k puisque la liste n'a pas nécessairement une longueur multiple de k).

Par exemple T=[2, 3, 7, 1, 5, 8, 9,11] est triée 3 par 3 puisque [2,3,7], [1,5,8] et [9, 11, /] sont triées. Mais elle n'est pas triée 4 par 4 puisque [2,3,7,1] n'est pas triée.

Programmer une fonction :


Entrée : une liste triée k par k (où k est un entier non nul)

Sortie : cette même liste triée 2k par 2k.

On utilisera la fonction fusion de l'exercice précédent.

Programmer le tri par fusion.

En utilisant ce qui précède, programmer le tri par fusion d'une liste.

Résolution de l'exercice "Programmer le tri par fusion".

Liste triée k par k.

La seule 'difficulté' est de ne pas oublier de tenir compte de la fin de liste avec le fait, notamment, que la longueur de la liste initiale n'est pas nécessairement multiple de k, ni de 2k.


def fusion(L, p, q, r) :
	L3 = []
	L1 = L[p:q]
	L2 = L[q:r]
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while L1 and L2 :
		if L1[0] < L2[0] : L3.append(L1.pop(0))
		else : L3.append(L2.pop(0))
			
	# une sous-liste étant vidée
	# on colle tout le contenu de l'autre
	# en queue de L3 
	if L1 : L3.extend(L1)
	else : L3.extend(L2)
			
	# on copie dans la liste L initiale
	# la fusion obtenue :
	del(L[p:q])
	L[p:q]=L3
		

def doublekTri(L,k) :
	p = 0
	q = min(p+k, len(L))
	r = min( q+k, len(L)) 
	while p<len(L)-1 :
		fusion(L, p, q, r)
		p=r
		q = min(p+k, len(L))
		r = min(q+k, len(L)) 




# exemple d'utilisation : 
L = [1,3, 2,8, 5,9,  -3,10,  1,5, 3]
print(L)
doublekTri(L,2)
print(L)

Le tri fusion.

On part du fait qu'une liste est initialement nécessairement triée 1 par 1. Et suivant le principe du tri fusion exposé dans le cours, on double à chaque étape la longueur des segments consécutifs triés.


from random import randint

def fusion(L, p, q, r) :
	L3 = []
	L1 = L[p:q]
	L2 = L[q:r]
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while L1 and L2 :
		if L1[0]<L2[0] : L3.append(L1.pop(0))
		else : L3.append(L2.pop(0))
			
	# une sous-liste étant vidée
	# on colle tout le contenu de l'autre
	# en queue de L3 
	if L1 : L3.extend(L1)
	else : L3.extend(L2)
			
	# on copie dans la liste L initiale
	# la fusion obtenue :
	del(L[p:q])
	L[p:q]=L3
		

def doublekTri(L,k) :
	p = 0
	q = min(p+k, len(L))
	r = min( q+k, len(L)) 
	while p<len(L)-1 :
		fusion(L, p, q, r)
		p=r
		q = min(p+k, len(L))
		r = min( q+k, len(L)) 


def trifusion(L) :
	k=1
	while k<len(L) :
		doublekTri(L,k)
		k*=2

# tirage au hasard d'une liste d'entiers de taille n
n=10 
L = [ randint(1, 3*n) for j in range(n) ]
print(L)
trifusion(L)
print(L)

Tri fusion récursif.

En utilisant la procédure de fusion ci-dessous prenant en entrée deux listes triées L1, L2 et retournant la liste fusion des deux précédentes, proposez une programmation récursive du tri par fusion.


def fusion(L1, L2) :
	L3 = []
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while L1 and L2 :
		if L1[0]<L2[0] : L3.append(L1.pop(0))
		else : L3.append(L2.pop(0))
			
	# une sous-liste étant vidée
	# on colle tout le contenu de l'autre
	# en queue de L3 
	L3=L3+L1+L2
	
	return L3


from random import randint

def fusion(L1, L2) :
	L3 = []
	
	# boucle posant en queue de L3
	# les min des têtes des sous-listes L1, L2
	while L1 and L2 :
		if L1[0]<L2[0] : L3.append(L1.pop(0))
		else : L3.append(L2.pop(0))
			
	# une sous-liste étant vidée
	# on colle tout le contenu de l'autre
	# en queue de L3 
	L3=L3+L1+L2
	
	return L3
			

def trifusion(L) :
	n=len(L)
	if n<= 1 : return L
	else : return fusion( trifusion(L[:n//2]), trifusion(L[n//2 : ] ) )

# tirage au hasard d'une liste d'entiers de taille n
n=10 
L = [ randint(1, 3*n) for j in range(n) ]
print(L)
L=trifusion(L)
print(L)