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.

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

p < q < r
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.

Une première version utilisant quelques raccourcis python (au risque de manipulations intermédiaires de listes consommatrices de temps et 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] :
			L3.append(L[i])
			i += 1
		else :
			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)

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 :

Paramètre d'entrée.: Une liste triée k par k (où k est un entier non nul).
Valeur retournée.: Cette même liste triée 2k par 2k.

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

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)

Programmer le tri par fusion.

En utilisant l'exercice précédent, programmer le tri par fusion d'une liste.

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)

Complexité du tri par fusion.

En raisonnant à partir du code de l'exercice précédent, majorer le nombre de comparaisons utilisées dans un tri par fusion.

Quel est le nombre maximal de comparaisons dans une fusion de deux listes de longueur k ?
Combien de fois la fonction doublekTri appelle-t-elle la fonction de fusion ? En déduire un majorant du nombre de comparaisons dans un appel de la fonction doublekTri.
Revoir l'exercice "regroupement par deux" de la fiche sur le logarithme et en déduire que le nombre de comparaisons peut être majoré par \( n \lceil \log_2(n) \rceil \) dans un tri par fusion.

Nombre de comparaisons dans une fusion.

Lorsqu'on fusionne deux listes triées L et M ayant respectivement a éléments et b éléments, on peut majorer le nombre de comparaisons par a+b.

A chaque comparaison, on élimine en effet un élément (le plus petit dans la comparaison). Donc après a+b comparaisons, on aura entièrement "vidé" les listes L et M et la fusion est nécessairement terminée.

Nombre de comparaisons dans un appel à la fonction `doublekTri`.

Le nombre de comparaisons utilisé lors de la fusion de deux segments de liste est majoré par le nombre d'éléments présents dans la réunion de ces deux segments d'après le décompte fait précédemment.

Et lorsqu'on applique doublekTri, les segments utilisés constituent une partition de la liste et un segment n'intervient que dans une fusion au plus. Le nombre de comparaisons est donc d'au plus \( n\) pour un appel de doublekTri.

Nombre de comparaisons dans un tri par fusion.

Dans l'exercice "regroupement par deux" de la fiche sur le logarithme, on voit que le nombre d'appels à doublekTri dans la fonction trifusion est égal à blog(n).

Le nombre de comparaisons est donc majoré par \( n \times \lceil \log_2(n) \rceil \).

Il nous resterait à compter les autres opérations élémentaires (affectations...), mais l'essentiel est déjà là : nous avons ici donner la démarche établissant qu'un tri par fusion est de complexité \( n \log(n) \).

Comparaison des complexités des tri par fusion et tri par sélection.

On suppose disposer d'un annuaire de la population française (soit environ 66.10⁶ personnes).

On cherche à trier cette liste avec un ordinateur cadencé à 3 GHz, une comparaison s'effectuant en dix cycles machine (en d'autres termes, une comparaison s'effectue en un temps égal à \( \frac{10}{3 \cdot 10^9} \) seconde).

Estimer le temps nécessaire avec un tri par sélection (environ \( \frac{1}{2} \times n^2 \) comparaisons pour une liste de taille \( n \)) puis pour un tri par fusion (environ \( n \log_2(n) \) comparaisons).

Même question avec la population mondiale (environ \( 7\cdot 10^9 \) personnes).

Tri sélection

\(\frac{1}{2} \times (66 \times 10^6)^2 \times \frac{10}{3 \cdot 10^9} \approx 7 \cdot 10^6 \text{ s}\)
soit environ \( 84 \text{ jours} \)

Tri fusion

\( 66 \times 10^6 \times \log_2(66 \times 10^6) \times \frac{10}{3 \cdot 10^9} \approx 6 \text{ s}\)

Et pour la population mondiale ?

Avec un tri sélection, on trouve plus de 2500 ans, et avec un tri par fusion, environ 12 minutes !

Vous comprenez maintenant pourquoi l'étude de la complexité d'un algorithme est primordial !

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)