Avancé
🧠 Fondamentaux
30 XP
0 personnes ont réussi
Tri rapide (quick sort)
Le tri rapide est souvent le plus utilise en pratique. Son idee : choisir un élément pivot, puis séparer tous les éléments en trois groupes.
Imagine que tu tries des eleves par taille. Tu choisis un eleve au hasard comme référence (le pivot). Tu demandes a ceux qui sont plus petits d'aller a gauche, ceux de meme taille de rester au milieu, et ceux plus grands d'aller a droite. Ensuite, tu tries recursivment le groupe de gauche et celui de droite.
L'astuce : on prend le dernier élément comme pivot (c'est le plus simple a implémenter).
En moyenne, le tri rapide est O(n log n), mais il peut etre O(n²) dans le pire cas (liste deja triee, mauvais pivot).
Écris une fonction tri_rapide(lst) qui retourne une nouvelle liste triee.
def tri_rapide(lst):
if len(lst) <= 1:
return lst
pivot = lst[-1]
inferieurs = [x for x in lst[:-1] if x < pivot]
egaux = [x for x in lst if x == pivot]
superieurs = [x for x in lst[:-1] if x > pivot]
return tri_rapide(inferieurs) + egaux + tri_rapide(superieurs)