Activités
activité 15.1
Appliquez l'algorithme de tri-fusion au tableau T = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Vous n'hésiterez pas à faire un schéma et à expliquer la fusion de 2 tableaux triés.
activité 15.2
Voici une implémentation du tri-fusion en Python :
def tri_fusion(tab):
def fusion(tab, p, q, r):
n1 = q-p+1
n2 = r-q
L = [0]*n1
R = [0]*n2
for i in range(n1):
L[i] = tab[...]
for j in range(n2):
R[j] = tab[...]
L.append(float("inf"))
R.append(float("inf"))
i = 0
j = ...
for k in range(p, r+1):
if L[i] <= R[j]:
tab[k] = ...
i = ...
else :
tab[k]=R[j]
j = ...
def tri_f(tab, p, r) :
if p < r:
q = (p + r) // ...
tri_f(tab, p, q)
tri_f(tab,... , r)
fusion(tab, p, q, ...)
tri_f(tab, p = 0, r = len(tab) - 1)
return tab
activité 15.3
Voici une autre implémentation possible du tri-fusion en Python.
def tri_fusion(tab):
n = len(tab)
if n > 1 :
mil = n // ...
L = tab[:mil]
R = tab[mil:]
tri_fusion(L)
tri_fusion(R)
i = 0
j = 0
k = 0
while i<len(L) and j<len(R):
if L[i] < R[...]:
tab[k] = L[...]
... = ... + 1
else :
tab[k] = R[...]
j = j + 1
... = ... + 1
while i < len(L):
tab[...] = L[i]
i = i + 1
k = k + 1
while j < len(...):
tab[k] = R[j]
j = j + 1
k = k + 1
Quelques informations pour vous aider :
Cette implémentation utilise le slicing. Le slicing permet de récupérer une partie d'une liste python en écrivant :
où L est une liste Python et S une autre liste Python contenant uniquement les éléments d'index "deb" à "fin" de la liste L (l'élément d'indice "deb" est inclus alors que l'élément d'indice "fin" est exclu). Voici un exemple : Dans l'exemple ci-dessus, on a S = [5, 7, 9]. On a bien l'élément d'indice 1 (c'est-à-dire 5) jusqu'à l'élément d'indice 3 (c'est-à-dire 9). Attention de ne pas oublier que l'élément d'indice 4 (c'est-à-dire 15) est exclu.Il est possible d'utiliser des "raccourcis" :
a exactement la même signification que : De la même manière : permet de récupérer tous les éléments de la liste L à partir de l'élément d'indice 3. Par exemple, pour : On a S = [7, 9, 15, 25].activité 15.4*
Nous avons vu que le tri fusion repose sur le principe algorithmique du "diviser pour régner", un autre algorithme de tri célèbre utilise aussi ce principe du "diviser pour régner" : le tri rapide (quicksort en anglais).
En vous aidant de la vidéo (en anglais, mais assez facilement compréhensible) dont le lien est donné ci-dessous (vous pouvez arrêter la vidéo à 18 minutes et 59 secondes), implémentez l'algorithme du tri rapide en Python