NSI (terminale) · Chapitre 6 · Application directe du cours
Tri rapide avec pivot aléatoire
Diviser pour régner · niveau 1 (application)
Énoncé
Tri rapide avec pivot aléatoire.
Modifier le tri rapide pour choisir un pivot aléatoire afin d'éviter le pire cas sur les tableaux déjà triés.
Corrigé
import random
def tri_rapide_alea(tab):
if len(tab) <= 1:
return tab
pivot = random.choice(tab)
petits = [x for x in tab if x < pivot]
egaux = [x for x in tab if x == pivot]
grands = [x for x in tab if x > pivot]
return tri_rapide_alea(petits) + egaux + tri_rapide_alea(grands)Le partitionnement en trois (petits, égaux, grands) gère efficacement les doublons.
100 % gratuit
Essaie le suivant avec le tuteur
- L'exercice suivant avec le tuteur, sans compte : il guide pas à pas, sans donner la réponse
- 7 autres exercices corrigés dans ce chapitre
- Les 2 QCM du chapitre, le premier sans compte
- Le podcast et la vidéo du chapitre : 2 minutes d'écoute sans compte
Sans compte : le cours, le premier QCM, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.