Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Méthode "diviser pour régner":======
----


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 [[les_fiches_revisions:langages_programmation:recursivite|récursivité]] sur laquelle cette méthode est souvent basée)

Comme son nom l'indique (ou pas), ce paradigme est séparés en trois étapes. 
  * **__DIVISER :__** sépare le problème initial en multiples petits problèmes.
  * **__RÉGNER :__** résolus les sous problèmes étant plus simples.
  * **__COMBINER :__** assemble les solutions des sous problèmes afin d'avoir la solution du problème initial

\\

L'algorithme de __tri-fusion__ est un algorithme de tri utilisant la méthode "diviser pour régner" et utilisant aussi la récursivité. Ainsi il est plus rapide et efficace ayant un complexité de "O(n.log(n))" :

<code>
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
</code>