Activités
activité 15.1
Résumez en quelques lignes le principe de la méthode "diviser pour régner"
activité 15.2
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.3
Implémentez en Python l'algorithme de tri-fusion. Vous testerez votre programme à l'aide du tableau suivant A = [23, 12, 4, 56, 35, 32, 42, 57, 3]
activité 15.4
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.5*
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