Tri rapide avec pivot aléatoire
Application directe du cours · niveau 1 (application) · NSI (terminale), chapitre 6 — Diviser pour régner
É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.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.