Ceci est une ancienne révision du document !
Cette méthode algorithmique permet de résoudre un problème. Tout d'abord, on divise ce problème en une multitude de petits problèmes, puis ces sous-problèmes étant plus simples, sont ensuite résolus, et on recombine enfin les petits problèmes résolus afin d'obtenir la solution du problème de départ. (je vous invite à voir la récursivité sur laquelle cette méthode est souvent basée)
Comme son nom l'indique (ou pas), ce paradigme est séparée en trois étapes.
L'algorithme de tri-fusion est un algorithme de tri utilisant la méthode “diviser pour régner” et utilisant aussi la récursivité:
VARIABLE A : tableau d'entiers L : tableau d'entiers R : tableau d'entiers p : entier q : entier r : entier n1 : entier n2 : entier 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 FIN