Diviser pour régner : tri fusion et récursivité (Bac NSI)
Mis à jour le · AprenAI
Diviser pour régner consiste à couper un problème en sous-problèmes plus petits, à les résoudre récursivement, puis à combiner les résultats. Dans les annales digitalisées du Bac NSI, le thème donne 3 sujets, tous en 2021 et 2022 : le tri fusion, le comptage des inversions d'un tableau et la création d'un labyrinthe, notés de 2 à 4 points.
- 8 sujets officiels
- 1,6 % des sujets
- 2021-2025 années
Comment fonctionne la méthode diviser pour régner ?
Le paradigme diviser pour régner se déroule toujours en trois temps. On divise : le problème de taille n est découpé en parties plus petites, souvent deux moitiés. On règne : chaque partie est résolue, en général par un appel récursif, jusqu'à un cas de base (liste de longueur 0 ou 1, grille d'une seule ligne ou colonne) qu'on traite directement. On combine : les résultats partiels sont fusionnés en une solution complète.
Le tri fusion en est l'exemple type. La fonction tri_fusion(L) renvoie L si len(L) <= 1. Sinon elle découpe L en deux listes avec moitie_gauche (indices strictement inférieurs à len(L) // 2) et moitie_droite (indices supérieurs ou égaux), trie chacune par appel récursif, puis fusionne les deux listes triées avec fusion. Pour L = [3, 5, 2, 7, 1, 9, 0] de longueur 7, moitie_gauche donne [3, 5, 2] et moitie_droite donne [7, 1, 9, 0] : la moitié gauche a un élément de moins quand la longueur est impaire. La fusion parcourt deux listes triées avec deux indices i1 et i2 : on compare e1 = L1[i1] et e2 = L2[i2], on ajoute à la liste résultat le plus petit (e1 si e1 <= e2) et on avance l'indice correspondant, jusqu'à épuisement.
Côté coût, la fusion de deux listes de tailles totales n demande de l'ordre de n comparaisons, et la taille est divisée par 2 à chaque niveau de récursion, soit environ log₂ n niveaux : le coût du tri fusion est en O(n log n), dit quasi-linéaire. Le tri par insertion ou par sélection est en O(n²), quadratique, donc moins efficace pour de grandes listes. Le tri par tas, mentionné dans un corrigé, est aussi en O(n log n).
La même idée sert à compter les inversions d'un tableau. Un couple d'indices (i, j) est une inversion quand i < j et tab[i] > tab[j] : le tableau [1, 6, 2, 7, 3] en compte trois, et [7, 6, 5, 3] en compte six. La méthode itérative est quadratique ; la méthode récursive divise le tableau en deux moitiés, compte les inversions de chacune, puis ajoute celles qui chevauchent les deux moitiés, calculées sur des moitiés triées. Le labyrinthe du sujet 2022 applique le même principe à une grille coupée en deux sous-grilles reliées par un passage, avec un cas de base quand la hauteur ou la largeur vaut 1.
- Diviser pour régner: Méthode qui découpe un problème en sous-problèmes indépendants, les résout récursivement puis combine leurs solutions.
- Cas de base: Situation simple traitée sans nouvel appel récursif, qui garantit l'arrêt de la récursion.
- Tri fusion: Tri qui coupe la liste en deux, trie chaque moitié récursivement puis fusionne les moitiés triées. Coût en O(n log n).
- Fusion: Opération qui construit une liste triée à partir de deux listes déjà triées en comparant leurs éléments de tête.
- Inversion: Couple d'indices (i, j) avec i < j tel que tab[i] > tab[j].
- Tranche (slice): Sous-liste obtenue avec tab[a:b] : indices de a inclus à b exclu.
À ne pas confondre sur diviser pour régner
- Tri fusion ≠ Tri par insertion: Le tri fusion divise la liste et coûte O(n log n) ; le tri par insertion décale les éléments un à un et coûte O(n²) dans le pire des cas.
- Division ≠ Fusion: Diviser découpe la liste (moitie_gauche, moitie_droite) ; fusionner combine deux listes déjà triées. Le tri a lieu pendant la fusion.
- O(n log n) ≠ O(n²): Pour de grandes valeurs de n, le rapport n log n / n² tend vers 0 : le tri fusion est asymptotiquement plus efficace.
- Récursif ≠ Itératif: Le comptage d'inversions itératif utilise deux boucles imbriquées (quadratique) ; la version récursive divise le tableau en deux.
- tab[:k] ≠ tab[k:]: tab[:k] contient les indices de 0 à k - 1 ; tab[k:] à partir de l'indice k. Les deux ensemble reconstituent tab.
| Algorithme | Principe | Coût en comparaisons |
|---|---|---|
| Tri fusion | Diviser en deux, trier, fusionner | O(n log n) |
| Tri par insertion | Insérer chaque élément dans la partie triée | O(n²) |
| Tri par sélection | Chercher le minimum et le placer | O(n²) |
| Comptage d'inversions itératif | Deux boucles imbriquées | O(n²) |
Mode Bac : ce qui rapporte des points
- Coût du tri fusion: O(n log n), dit quasi-linéaire ; chaque niveau coûte de l'ordre de n comparaisons et il y a environ log₂ n niveaux.
- Comparer avec un autre tri: Tri par insertion ou par sélection : O(n²), donc plus coûteux que le tri fusion pour de grandes valeurs de n.
- Cas de base: len(L) <= 1 pour un tri ; haut == 1 ou long == 1 pour la grille du labyrinthe.
- Fusion: Si e1 <= e2, ajouter e1 et avancer i1 ; sinon ajouter e2 et avancer i2.
- Inversion: Deux conditions à vérifier : i < j et tab[i] > tab[j].
- Combiner pour les inversions: Résultat = inversions de la moitié gauche + inversions de la moitié droite + inversions entre les deux moitiés.
Quels exercices sont tombés sur diviser pour régner ?
Dans les annales digitalisées, le thème compte 3 sujets : deux en 2021 (Métropole France 1 et Métropole Candidat libre 1) et un en 2022 (Métropole France 2). Deux sont des exercices complets de 4 points, le troisième est un extrait de 2 points. Les questions commencent presque toujours par le coût de l'algorithme, puis passent au code.
- Tri fusion : coût, trace et fusion (1): Ordre de grandeur du coût, comparaison avec un autre tri, affichages produits par tri_fusion([7, 4, 2, 1, 8, 5, 6, 3]), puis complétion du code de fusion (Métropole France 1, 2021, exercice 4, 4 points).
- Comptage des inversions (1): Partie A itérative avec une fonction qui compte les éléments plus petits après l'indice i, complexité quadratique, puis version récursive avec moitie_gauche et moitie_droite (Métropole Candidat libre 1, 2021, exercice 5, 4 points).
- Création d'un labyrinthe (1): Compléter le cas de base de creer_labyrinthe (hauteur 1 ou longueur 1) et dérouler l'algorithme sur une grille 4 × 8 (Métropole France 2, 2022, exercice 5, questions 5 et 6, 2 points).
- Exercice 4 · Métropole 2021 (sujet 1) · Tri fusion : coût, trace et fusion
- Exercice 5 · Métropole Candidat libre 2021 (sujet 1) · Comptage des inversions
- Exercice 5 - Questions 5 et 6 : Diviser pour régn… · Métropole 2022 (sujet 2) · Création d'un labyrinthe
Entraîne-toi : Diviser pour régner (8 sujets officiels)
Tous les sujets de NSI sur « Diviser pour régner » (2021-2025), avec le corrigé.
Comment tracer et écrire un algorithme diviser pour régner ?
Exemple : Métropole France 1, 2021, exercice 4. On demande les affichages de tri_fusion([7, 4, 2, 1, 8, 5, 6, 3]), sachant que la fonction affiche L uniquement quand len(L) > 1, avant de se rappeler sur la moitié gauche puis sur la moitié droite.
- Appel initial: La liste complète a 8 éléments : on affiche [7, 4, 2, 1, 8, 5, 6, 3].
- Moitié gauche, récursivement: On affiche [7, 4, 2, 1], puis sa moitié gauche [7, 4]. Ses moitiés [7] et [4] ont une longueur de 1 : aucun affichage. Puis [2, 1], dont les moitiés ne s'affichent pas non plus.
- Moitié droite: On affiche [8, 5, 6, 3], puis [8, 5], puis [6, 3].
- Résultat à rédiger: Six lignes : [7, 4, 2, 1, 8, 5, 6, 3] ; [7, 4, 2, 1] ; [7, 4] ; [2, 1] ; [8, 5, 6, 3] ; [8, 5] ; [6, 3]. L'ordre est celui d'un parcours en profondeur : gauche avant droite.
- Écrire la fusion: Initialiser L = [], i1 = 0 et i2 = 0 ; tant que les deux indices sont dans les listes, comparer et ajouter le plus petit ; ajouter ensuite le reste de la liste non épuisée.
- Répondre sur le coût: Chaque niveau de récursion fait de l'ordre de n comparaisons, il y a log₂ n niveaux : O(n log n).
Quelles erreurs éviter avec diviser pour régner ?
Les corrigés de ces sujets sont des réponses types sans barème détaillé. Ils montrent néanmoins ce qui doit apparaître dans la copie : un ordre de grandeur exact, un cas de base et la bonne borne dans les boucles.
- Oublier le cas de base: Sans len(L) <= 1 (ou haut == 1 / long == 1), la récursion ne s'arrête pas.
- Mal découper en deux moitiés: Avec une longueur impaire, la moitié gauche et la moitié droite n'ont pas la même taille : pour 7 éléments, 3 et 4 avec moitie_gauche du sujet 2021.
- Mauvaises bornes dans le labyrinthe: Pour une ligne de long cellules à partir de la colonne colonne, il y a long - 1 passages : range(colonne, colonne + long - 1).
- Confondre n log n et n²: Le tri fusion est quasi-linéaire ; le tri par insertion est quadratique. Indiquez bien la comparaison demandée.
- Afficher dans le mauvais ordre: Dans la trace d'un algorithme récursif, la moitié gauche est entièrement traitée avant la moitié droite.
- Compter deux fois une inversion: Pour les paires, la boucle interne commence à i + 1 ; sinon on compare un élément à lui-même ou on double les paires.
Comment réviser diviser pour régner ?
- Savoir écrire le tri fusion en entier: Découpage, cas de base, fusion, assemblage. Écrivez-le sans notes jusqu'à ce que ce soit automatique.
- Tracer à la main: Entraînez-vous avec des listes de 4, 6 et 8 éléments, en notant l'ordre des appels.
- Apprendre les coûts: O(n log n) pour tri fusion et tri par tas, O(n²) pour insertion et sélection, O(log n) pour la dichotomie.
- Revoir les tranches Python: tab[:k], tab[k:], len(tab) // 2 : les erreurs d'indices sont les plus fréquentes.
- Faire les trois exercices officiels: Inversions, tri fusion et labyrinthe, sur AprenAI, avec la solution rédigée pour comparer.
Quelle est la complexité du tri fusion ?
Elle est en O(n log n) comparaisons : la liste est divisée en deux à chaque niveau (environ log₂ n niveaux) et chaque niveau demande de l'ordre de n comparaisons pour fusionner.
Comment fonctionne la fusion de deux listes triées ?
On garde deux indices, un par liste. À chaque étape, on compare les deux éléments courants, on ajoute le plus petit au résultat et on avance l'indice de la liste d'où il vient.
Qu'est-ce qu'une inversion dans un tableau ?
C'est un couple d'indices (i, j) avec i < j et tab[i] > tab[j]. Le tableau [7, 6, 5, 3] en contient six, alors que [1, 6, 2, 7, 3] en contient trois.
Pourquoi le tri fusion est-il plus efficace que le tri par insertion ?
Parce que son coût est quasi-linéaire alors que celui du tri par insertion est quadratique dans le pire des cas ; l'écart devient énorme pour de grandes listes.
Combien de sujets du Bac NSI portent sur diviser pour régner ?
Dans les annales digitalisées, 3 sujets : deux en 2021 et un en 2022, de 2 à 4 points chacun.
Plus sur l'épreuve de NSI
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Arbres et arbres binaires de recherche · 50 sujets
- Graphes : modélisation et parcours · 27 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Récursivité · 24 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Programme comme donnée, calculabilité et décidabilité · 2 sujets
- Programmation dynamique · 7 sujets
- Recherche textuelle et algorithme de Boyer-Moore · 3 sujets
- Coût des algorithmes, tris et recherche · 23 sujets