Chapitre 9 : Diviser pour régner.
Rappel :
Vous avez vu l'année dernière le tri par insertion et le tri par selection et tous les deux avaient une complexité en \(\mathcal{O}\left(n^2\right)\).
1. Diviser pour régner:
A copier dans le cahier.
L'expression "diviser pour régner" en informatique est utilisée pour décrire un algorithme fractionnant un problème, ou des données en éléments plus petits afin de les traiter.
2. Exercice : (sujet 9 - 2025)
On s’intéresse à la recherche dichotomique dans un tableau trié d’entiers.
Compléter la fonction suivante en respectant la spécification.
Exemples :
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27)
FalseTests :
Affichage :
Console:
3. Le tri par fusion
A copier dans le cahier.
Le tri par fusion est un algorithme de tri d'une liste qui fonctionne par récurrence à l'aide du principe de diviser pour régner.
Sa complexité est en \(\mathcal{O}\left(n \log(n)\right)\).
4. Exercice : fusion!
Compléter la fonction fusion(liste1,liste2), qui prend comme paramètres deux listes triées et qui renvoie une liste triée composée des élements des deux autres.
def fusion(liste1,liste2):
'''
fusion prend deux listes triées et retourne une grand liste triée contenant les éléments des deux autres.
'''
final=[] #liste qui sera retournée
curseur1=0 #curseur de la liste1
curseur2=0 #curseur de la liste2
while ...................................................... : #tant que il reste des éléments non traités dans une des deux listes
if ............... : #le plus petit élément est dans la liste 1
final.append(liste1[curseur1])
curseur1+=1
else: #le plus petit élément est celui de la liste 2
......................
......................
if ......................... : #il reste des éléments dans la liste 2 à traiter
for i in range(curseur2,len(liste2)):
final.append(.......)
else : #il reste des éléments dans la liste 1 à traiter
for i in range(curseur1,len(liste1)):
final.append(.......)
return finalOn pourra tester notre fonction fusion à l'aide des listes suivantes :
listeA=[2,5,7,8,9,11,13,15,19,21,25,29,35,38,39,40,52,69,78,89]
listeB=[3,4,5,7,12,14,15,18,23,30,32,33,34,42,53]5. Exercice : tri fusion
Compléter la fonction tri_par_fusion(liste) à l'aide de la fonction de l'exercice précédent.
def tri_par_fusion(liste):
if ............ : # Il y a un élément dans la liste ou moins.
return liste
else:
moitie=...... # indice correspondant au milieu de la liste
gauche=tri_par_fusion(.............)
droite=tri_par_fusion(.............)
return fusion(gauche,droite)6. Exercice :
A faire dans le cahier.
Ce code a permis de générer les 3 images ci-dessous :
Il peut sembler que les courbes soient similiaires mais :
- Comparer les performances de chaque tri.
- A quelle courbe vue en seconde ressemble les deux premières ci-dessus?
- Quel est l'aspect de la troisième courbe?
- Dans les deux premières courbes:
- Prendre deux points de la courbe dont les abscisses sont à peu près le double l'une de l'autre.
- Calculer une approximation du rapport de ces ordonnées.
- Dans les deux premières courbes:
- Prendre deux points de la courbe dont les abscisses sont à peu près le triple l'une de l'autre.
- Calculer une approximation du rapport de ces ordonnées.
- Dans les deux premières courbes:
- Prendre deux points de la courbe dont les abscisses sont à peu près le quadruple l'une de l'autre.
- Calculer une approximation du rapport de ces ordonnées.
- Dans la troisième courbe:
- Prendre deux points de la courbe dont les abscisses sont à peu près le quadruple l'une de l'autre.
- Calculer une approximation du rapport de ces ordonnées.
7. A retenir !
A copier dans le cahier.
Les tris par insertion et par selection sont de complexités quadratiques en \(\mathcal{O}\left(n^2 \right)\).
Le tri par fusion est de complexité linéarithmique en \(\mathcal{O}\left(n \log(n)\right)\).