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.

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.

À ne pas confondre sur diviser pour régner

AlgorithmePrincipeCoût en comparaisons
Tri fusionDiviser en deux, trier, fusionnerO(n log n)
Tri par insertionInsérer chaque élément dans la partie triéeO(n²)
Tri par sélectionChercher le minimum et le placerO(n²)
Comptage d'inversions itératifDeux boucles imbriquéesO(n²)

Mode Bac : ce qui rapporte des points

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.

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.

  1. Appel initial: La liste complète a 8 éléments : on affiche [7, 4, 2, 1, 8, 5, 6, 3].
  2. 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.
  3. Moitié droite: On affiche [8, 5, 6, 3], puis [8, 5], puis [6, 3].
  4. 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.
  5. É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.
  6. 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.

Comment réviser diviser pour régner ?

  1. Savoir écrire le tri fusion en entier: Découpage, cas de base, fusion, assemblage. Écrivez-le sans notes jusqu'à ce que ce soit automatique.
  2. Tracer à la main: Entraînez-vous avec des listes de 4, 6 et 8 éléments, en notant l'ordre des appels.
  3. 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.
  4. Revoir les tranches Python: tab[:k], tab[k:], len(tab) // 2 : les erreurs d'indices sont les plus fréquentes.
  5. 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