Essayez d'écrire une fonction python récursive prenant en entrée une liste de nombres et retournant en sortie une liste triée contenant les mêmes nombres que la liste d'entrée. Cette fonction de tri devra s'appuyer sur une utilisation de la fonction suivante :
def fusion(A, B) :
C = []
while A != [] and B != [] :
if A[0] < B[0] : C.append(A.pop(0))
else : C.append(B.pop(0))
return C + A + B
- ISN
- principe
- un code
- CAPES
Le tri fusion est au programme de l'enseignement de la spécialité ISN.
La fonction proposée est utile lorsque A et B sont elles mêmes des listes triées en ordre croissant : la fonction retourne alors une fonction C triée en ordre croissant et constituée des éléments de A et des éléments de B.
Principe du "tri fusion" :
- Lorsque la liste est de longueur au plus 1, elle est triée.
- Sinon la liste à retourner est la fusion du tri de la première moitié de liste et du tri de la seconde moitié de liste.
def fusion(A, B) :
C = []
while A != [] and B != [] :
if A[0] < B[0] : C.append(A.pop(0))
else : C.append(B.pop(0))
return C + A + B
def tri(liste) :
if len(liste) < 2 : return liste
else :
milieu = len(liste)//2
return fusion( tri(liste[:milieu]), tri(liste[milieu:]) )
L = [2,6,1,5,4,1,2,3,4,1]
print(tri(L))
Une partie du problème 2 du CAPES de mathématiques 2017 porte sur le tri fusion.