Illustration.

Vous pouvez observer ci-dessous la fusion de deux listes triées en action.

On dispose de deux listes triées : une verte et une jaune.

Cliquez sur le bouton "Manuel" pour dérouler les étapes à votre rythme et comprendre ces étapes d'exécution.

Le bouton "Automate" enchaîne les étapes avec un intervalle de temps d'environ 3 secondes entre deux étapes (vous pouvez réduire ce temps en cliquant sur la petite flèche du formulaire contenant le nombre 3000).

Pour accélérer l'automate, régler ici le temps (en ms) qui sépare deux étapes :

formulation de l'algorithme.

Formulez, en français, l'algorithme de fusion de deux listes triées.

une formulation

Entrée	Deux listes triées L1, L2.
Initialisation	L = [] (liste vide)
Traitement	On sélectionne le plus petit des deux éléments en tête des deux listes L1, L2. On place cet élément en queue de la liste L et on le supprime de la tête de sa liste d'origine. On reprend au point 1 tant que les deux listes L1, L2 sont non vides. Si L1 est vide, on peut placer tous les éléments de L2 en queue de L. Si L2 est vide, on peut placer tous les éléments de L1 en queue de L.
Sortie	L, liste triée contenant tous les éléments des deux listes d'entrée.

programmer.

Écrire un programme python :

Entrée	Deux listes triées L1, L2.
Sortie	L, liste triée contenant tous les éléments des deux listes d'entrée.

Le principe utilisé devant être, bien entendu, celui de la fusion exposé ci-dessus.

un code possible

On rappelle que liste.pop(0) (où liste est du type list) retourne l'élément de tête de la liste tout en supprimant cet élément de la liste.


from random import randint


def fusion(liste1, liste2) :
	L = []
	while liste1 != [] and liste2 != [] :
		if liste1[0] < liste2[0] :
			L.append(liste1.pop(0))
		else : 
			L.append(liste2.pop(0))
	# on 'concatène' L, liste1, liste2
	# (l'une des listes liste1, liste2 étant vide à ce stade)
	return L + liste1 + liste2


if __name__ == '__main__' :

	# tirage  de listes au hasard pour les entrées :
	L1 = [ randint(1,100) for _ in range(randint(5,15))]
	L2 = [ randint(1,100) for _ in range(randint(5,15))]
	# tri de ces deux listes :
	L1.sort()
	L2.sort()
	# affichage pour contrôle visuel après exécution :
	print("La liste L1 : ")
	print(L1)
	print("La liste L2 : ")
	print(L2)
	#fusion des deux listes :
	L = fusion(L1, L2)
	# affichage du résultat :
	print("Liste résultant de la fusion : ")
	print(L)

programmer.

Écrire un programme python :

Entrée	Une liste Liste telle que la première partie (de l'indice 0 à l'indice d-1) soit triée (ordre croissant) et la seconde partie (de l'indice d à l'indice len(Liste)-1) soit triée (ordre croissant). d est la seconde entrée.
Sortie	L, liste triée contenant tous les éléments de la liste d'entrée.

Le principe utilisé sera celui de la fusion. On s'interdira de créer des listes autre que la liste L.

un code possible


from random import randint


def fusion(Liste, d) :
	L = []
	i, j  = 0, d
	while i != d and j != len(Liste) :
		if Liste[i] < Liste[j] :
			L.append(Liste[i])
			i += 1
		else :
			L.append(Liste[j])
			j += 1
	for k  in range(i,d) :
		L.append(Liste[k])
	for k  in range(j,len(Liste)) :
		L.append(Liste[k])
	return L  
		

 


if __name__ == '__main__' :

	# tirage  de listes au hasard pour les entrées :
	L1 = [ randint(1,100) for _ in range(randint(5,15))]
	L2 = [ randint(1,100) for _ in range(randint(5,15))]
	# tri de ces deux listes :
	L1.sort()
	L2.sort()
	# affichage pour contrôle visuel après exécution :
	print("La liste L1 : ")
	print(L1)
	print("La liste L2 : ")
	print(L2)
	# liste concaténée :
	L = L1 + L2
	print("Liste en deux parties : ")
	print(L)
	#fusion des deux listes :
	L = fusion(L, len(L1))
	# affichage du résultat :
	print("Liste résultant de la fusion : ")
	print(L)

fusion de deux segments de liste.

Programmer l'algorithme suivant :

Entrée	Une liste L de nombres, trois entiers p, q, r tels que : p < q < r les sous-listes [Lp, Lp+1, ..., Lq-1] et [Lq, Lq+1, ..., Lr-1] sont triées.
Sortie	La liste L dans laquelle les sous-listes [Lp, Lp+1, ..., Lq-1] et [Lq, Lq+1, ..., Lr-1] ont été fusionnées.

un code possible


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)

doubler la taille des segments triés.

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)
Effet	la liste initiale est triée 2k par 2k en sortie de fonction

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

un code possible

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)