La méthode « Diviser pour régner » est un paradigme algorithmique puissant, souvent utilisé pour résoudre des problèmes complexes de manière élégante et efficace. L’idée est de décomposer un problème en plusieurs sous-problèmes, de les résoudre individuellement, puis de combiner leurs solutions pour obtenir la solution du problème initial.
Ce processus se décompose en trois phases principales :
- DIVISER : Le problème initial est scindé en plusieurs sous-problèmes plus petits, généralement de nature similaire à l’original.
- RÉGNER : Chaque sous-problème est résolu, souvent de manière récursive. La clé est que ces sous-problèmes sont plus simples à gérer que le problème de départ.
- COMBINER : Les solutions des sous-problèmes sont fusionnées pour construire la solution finale du problème d’origine.
Les algorithmes qui emploient cette approche sont très souvent de nature récursive. Un exemple classique de cette méthode est le tri-fusion.
Le Tri-Fusion
Présentation
Le tri-fusion est un algorithme de tri efficace qui repose sur le principe « Diviser pour régner ». Il prend un tableau non trié en entrée et renvoie le même tableau, mais cette fois, dans l’ordre croissant.
Voici une implémentation simplifiée en pseudo-code des deux fonctions qui composent cet algorithme : FUSION et TRI-FUSION.
VARIABLE
A : tableau d'entiers
L, R : tableaux d'entiers
p, q, r, n1, n2 : entiers
k, i, j : entiers
DEBUT
FUSION (A, p, q, r):
n1 ← q - p + 1
n2 ← r - q
créer tableau L[1..n1+1] et R[1..n2+1]
pour i ← 1 à n1:
L[i] ← A[p+i-1]
fin pour
pour j ← 1 à n2:
R[j] ← A[q+j]
fin pour
L[n1+1] ← ∞
R[n2+1] ← ∞
i ← 1
j ← 1
pour k ← p à r:
si L[i] ⩽ R[j]:
A[k] ← L[i]
i ← i + 1
sinon:
A[k] ← R[j]
j ← j + 1
fin si
fin pour
fin FUSION
TRI-FUSION(A, p, r):
si p < r:
q = (p + r) // 2
TRI-FUSION(A, p, q)
TRI-FUSION(A, q+1, r)
FUSION(A, p, q, r)
fin si
fin TRI-FUSION
visuellement ça donne ça :
L’appel initial pour trier un tableau A est TRI-FUSION(A, 1, A.longueur). Notez que dans cet algorithme, la fonction TRI-FUSION gère la phase de DIVISER, tandis que la fonction FUSION combine les phases de RÉGNER et de COMBINER.
Un aspect intéressant du tri-fusion est que la phase de « Régner » est trivialement simple : le processus de division se poursuit jusqu’à ce que les sous-problèmes ne contiennent qu’un seul élément. Trier un tableau d’un seul élément ne demande aucune opération, ce qui simplifie grandement la tâche.
La véritable magie opère lors de la phase de fusion. Imaginons que nous ayons deux tableaux déjà triés, B et C, et que nous souhaitions les fusionner en un nouveau tableau T. On compare simplement le premier élément de B avec le premier de C, on ajoute le plus petit des deux à T, puis on recommence avec les éléments restants. On continue jusqu’à ce que l’un des tableaux soit vide, puis on ajoute les éléments restants de l’autre tableau à la fin de T.
Complexité
Bien que le calcul rigoureux soit hors de la portée de ce cours, nous pouvons en estimer la complexité de manière intuitive. La phase de division, où les tableaux sont coupés en deux à plusieurs reprises, est liée à la fonction logarithmique en base 2, soit log_2(n). La phase de fusion, pour un tableau de n éléments, nécessite un nombre de comparaisons proportionnel à n. En combinant ces deux observations, nous arrivons à une complexité approximative de l’ordre de O(nlog(n)).
Comme le montre la comparaison des courbes, un algorithme en O(nlog(n)) est beaucoup plus performant pour de grandes valeurs de n qu’un algorithme en O(n²), comme le tri par insertion ou le tri par sélection.
Retour sur la dichotomie
Présentation
C’est une méthode pour trouver un nombre N dans une liste triée si elle y est présente ou pour prouver son absence. Le principe est de regarder la valeur centrale, soit c’est celle qu’on cherche soit la valeur trouvée nous permettra de déterminer dans laquelle des sous listes de part et d’autre de la valeur devrait se situer N. Une fois fait on applique la même démarche sur la sous liste en question. On continuera jusqu’à soit tomber sur N ou obtenir une liste ne divise cette sous liste et on repère dans laquelle des parties devrait se situer la valeur. On continue, avec des sous listes de plus en plus petites et se dirigeant progressivement vers des listes vides. Soit on tombe sur N avant cela, sinon la valeur n’est pas présente. Cette recherche repose sur le principe « Diviser pour régner ».
exercice (corrigé ici)
compléter le code ci dessous
def recherche(t, v, g, d):
"""renvoie une position de v dans t[g..d],
supposé trié, et None si elle ne s’y trouve pas"""
...
def recherche_dichotomique(t, v):
"""renvoie une position de v dans le tableau t,
supposé trié, et None si elle ne s’y trouve pas"""
return ...
L’appel initial pour trier un tableau A est TRI-FUSION(A, 1, A.longueur). Notez que dans cet algorithme, la fonction TRI-FUSION gère la phase de DIVISER, tandis que la fonction FUSION combine les phases de RÉGNER et de COMBINE
Activités et Exercices
Activité 1
Appliquez l’algorithme de tri-fusion au tableau T= [23, 12, 4, 56, 35, 32, 42, 57, 3]. Vous pouvez créer un schéma et expliquer en détail la fusion de deux tableaux triés.
Activité 2
Complétez le code Python suivant pour la fonction de tri-fusion :
def tri_fusion(tab):
# Fonction pour fusionner deux sous-tableaux triés
def fusion(tab, p, q, r):
n1 = q - p + 1
n2 = r - q
# On crée deux tableaux temporaires, L et R
L = [0] * n1
R = [0] * n2
# On remplit les tableaux L et R
for i in range(n1):
L[i] = tab[p + i]
for j in range(n2):
R[j] = tab[q + j + 1]
# On ajoute un 'sentinelle' (une valeur très grande) à la fin de chaque tableau
# Cela nous permet d'éviter de vérifier si un tableau est vide
L.append(float("inf"))
R.append(float("inf"))
i = 0 # Indice pour le tableau L
j = 0 # Indice pour le tableau R
# On parcourt le tableau original pour y placer les éléments triés
for k in range(p, r + 1):
if __________: # Quelle est la condition pour savoir quel élément choisir ?
tab[k] = L[i]
i = i + 1
else:
tab[k] = R[j]
j = j + 1
# Fonction principale récursive pour le tri
def tri_f(tab, p, r):
# Quelle est la condition pour arrêter la récursion ?
if __________:
# On calcule le milieu
q = _________
# 1. On trie la première moitié du tableau
tri_f(tab, p, q)
# 2. On trie la deuxième moitié du tableau
tri_f(tab, q + 1, r)
# 3. On fusionne les deux moitiés triées
fusion(tab, p, q, r)
# Appel initial de la fonction de tri
tri_f(tab, p=0, r=_________) # De quelle borne à quelle borne allons-nous trier le tableau ?
return tab
Activité 3
Complétez cette autre version du tri-fusion en Python, en utilisant le « slicing » :
def tri_fusion_slice(tab):
n = len(tab)
# Condition d'arrêt de la récursion
if __________: # Quand arrêtons-nous de diviser le tableau ?
# Calcul du point milieu pour diviser le tableau
mil = _________
# On divise le tableau en deux sous-tableaux (slicing)
L = tab[:mil]
R = tab[mil:]
# Appels récursifs pour trier chaque moitié
tri_fusion_slice(L)
tri_fusion_slice(R)
# Indices pour parcourir les tableaux L, R et le tableau final
i = 0
j = 0
k = 0
# Boucle principale de fusion : on compare et on place les éléments
while i < len(L) and j < len(R):
if __________: # Quelle est la condition pour choisir l'élément de L ?
tab[k] = L[i]
i += 1
else:
tab[k] = R[j]
j += 1
k += 1
# Boucles pour ajouter les éléments restants (s'il y en a)
while i < len(L):
tab[k] = L[i]
i += 1
k += 1
while __________: # Quelle est la condition pour ajouter les éléments restants de R ?
tab[k] = R[j]
j += 1
k += 1
Activité 4
En vous basant sur la vidéo disponible à cette adresse, implémentez l’algorithme de tri rapide (Quicksort) en Python, un autre algorithme basé sur le principe « Diviser pour régner ».
Exercices
- Exercice 1 : Donnez la séquence des appels à la fonction de recherche dichotomique du cours pour les appels
recherche_dichotomique([0,1,1,2,3,5,8,13,21], 13)etrecherche_dichotomique([0,1,1,2,3,5,8,13,21], 12). - Exercice 2 : Quelles sont les deux listes renvoyées par une fonction
coupe()à laquelle on passe la liste[8, 1, 3, 0, 1, 2, 5]? L’ordre relatif est-il préservé ? Est-ce important ? - Exercice 3 : Réécrivez la fonction
fusionen utilisant une bouclewhileau lieu de la récursivité. - Exercice 4 : Le problème des Tours de Hanoï est un jeu célèbre impliquant trois tiges et des disques de tailles différentes. Écrivez une fonction
hanoi(n)qui affiche la solution pour n disques. - Exercice 5 : Combien de déplacements élémentaires faut-il au total pour déplacer N disques de la tour de départ à la tour d’arrivée dans le problème des Tours de Hanoï ?
- Exercice 6 : Réécrivez l’exercice 4 en utilisant des piles (voir chapitre 5).
- Exercice 7 : Écrivez une fonction qui effectue la rotation d’une image de 90 degrés en utilisant le principe « Diviser pour régner ». indications et voir photo plus bas.
- Exercice 8 : Appliquez le principe « Diviser pour régner » pour multiplier deux entiers en utilisant la méthode de Karatsuba.
Ping : Terminale NSI 2025-26 – Maths & Informatique