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 repartit( liste ) :
P = []
G = []
for x in liste[1:] :
if x < liste[0] : P.append(x)
else : G.append(x)
return P, G
- principe
- un code
La fonction proposée renvoie la liste P des éléments de L[1:] qui sont inférieurs à L[0] et la liste G des éléments de L[1:] qui sont supérieurs ou égaux à L[0].
Principe du "tri rapide" :
- Lorsque la liste est vide, elle est triée.
- Sinon la liste à retourner est la concaténation de la liste P triée, de la liste ne contenant que L[0] et de la liste G triée.
def repartit( liste ) :
P = []
G = []
for x in liste[1:] :
if x < liste[0] : P.append(x)
else : G.append(x)
return P, G
def quick( liste ) :
if liste == [] : return liste
else :
P, G = repartit(liste)
return quick(P) + [liste[0]] + quick(G)
L = [2,1,5,8,1,3,6,4,1,2]
print(quick(L))